An exact algorithm for minimizing a sum of Euclidean norms on rays in 2D and 3D

Numerical Functional Analysis and Optimization, 36(4) (2015), 405-418
http://dx.doi.org/10.1080/01630563.2015.1013549

This article describes an exact algorithm that runs in O(k^2) time for minimizing a sum of Euclidean norms, based on the idea of the method of orienting curves (introduced by Phu for solving optimal control problems with state constraints). The concepts "final lines" and "orienting lines" for the problem of minimizing a sum of Euclidean norms are introduced, and we show that the exact solution of the problem is determined by orienting lines and a final line. A comparison with the numerical solution of the same problem is presented.