Finding the nearest point in A polytope

Abstract

A terminating algorithm is developed for the problem of finding the point of smallest Euclidean norm in the convex hull of a given finite point set in Euclidean n-space, or equivalently for finding an "optimal" hyperplane separating a given point from a given finite point set. Its efficiency and accuracy are investigated, and its extension to the separation of two sets and other convex programming problems described. © 1976 The Mathematical Programming Society.