Computational geometry and linear programs

A collection of linear program (LP) formulations is presented for constructing and analyzing the convex hull of a given set of points and some related problems. The collection includes face identification, extreme set determination, checking for an interior point, identification of a cone containing no points other than its own vertex in general dimensional space. The problems of determining planar barycenter coordinates of two polygons, and data depth computation useful in bivariate statistical analysis are also included. The proposed LP unified approach enables us to use efficient solution algorithms to solve and perform sensitivity analysis for these related topics with many diverse applications. Small illustrative numerical examples are presented.