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.

CEMAT - Center for Computational and Stochastic Mathematics