Computation of Reduced Convex Hulls

Abstract

The idea of a reduced convex hull has been presented by geometric interpretations of Support Vector Machines (SVMs). A reduced convex hull is the set of all convex combinations of a set of points where the weight that may be assigned to any one point is constrained from above by a constant. This study decouples reduced convex hulls from their SVM origins and enables them to be built independently. We present two algorithms for computing reduced convex hulls: a simple recursive algorithm for points in the plane and an algorithm for points in any dimensional space. Upper bounds on the number of vertices and facets in a reduced convex hull are used to analyse the algorithms' worst-case complexity.