Finding the closest point to the origin in the convex hull of a discrete set of points

Finding the closest point to the origin in the convex hull of a discrete set of points

0.00 Avg rating0 Votes
Article ID: iaor1994702
Country: United Kingdom
Volume: 20
Issue: 4
Start Page Number: 363
End Page Number: 370
Publication Date: May 1993
Journal: Computers and Operations Research
Authors: ,
Keywords: computational analysis
Abstract:

This paper presents a specialized algorithm for finding a point in the convex hull of a given finite collection of discrete points that is closest to the origin. Such problems find applications in nondifferentiable optimization, statistics, approximation theory, and linear programming. The algorithm presented is easy to implement, has minimal storage requirements, and effectively controls the size and complexity of the subproblems solved. The authors prove convergence of the algorithm, and show how to solve the subproblems in closed-form. A computational comparison with a popular competing method exhibits an increased advantage for the proposed algorithm with an increase in problem size, except for highly ill-conditioned problems.

Reviews

Required fields are marked *. Your email address will not be published.