Computing the vector in the convex hull of a finite set of points having minimal length

Abstract

In order to compute descent directions for nondifferentiable functions it is necessary to determine the vector x ^∗in the convex hull of a given finite point set having minimal length.This general problem has also applications in various other fields. We describe an algorithm solving this problem for (large) point sets in the plane and in three-dimensional space, moreover this method can be extended to arbitrary dimensions. It turns out that this algorithm has a quadratic worst case complexity and a linear average case complexity in three-dimensional space

Keywords:

• Convex Hull
• Minimal Distance
• Computational Geometry
• Computational Complexity