An Exact Algorithm for Minimizing a Sum of Euclidean Norms on Rays in 2D and 3D

摘要

This article describes an exact algorithm that runs in O(k (2)) time for minimizing a sum of Euclidean norms , where t ( i ) >= a ( i ) > 0, p ( i ): DOUBLE-STRUCK CAPITAL R-1 -> DOUBLE-STRUCK CAPITAL R-2 (i = 1, horizontal ellipsis , k) are linear, k >= 3, based on the idea of the method of orienting curves (introduced by Phu in [15] 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.