| The convex hull of a set X of n points in m-dimensional space is a polytope P . The frame XE of these points is the set of extreme points of P . The problem of identifying the frame plays a central role in optimization theory, economics, computational geometry, data mining, and statistics.;The standard unembellished approach to finding the elements of XE consists of solving n linear programs with m rows and n -- 1 columns, differing only in that a designated point of X has become the right-hand side of a structural equality constraint and all other points appear as columns on the left.;An alternative approach is an algorithm previously developed by Jose Dula and Richard Helgason. It employs projection onto a developing partial convex hull instead of a linear programming solution and can be divided into three major steps: preprocessing, projection, and resolution. The major contribution of this dissertation is the development and validation of four new enhancements to the different steps of the Dula and Helgason algorithm: an enhancement to the preprocessing step involving the solution of several 2-dimensional convex hull subproblems, two enhancements to the resolution step which we have named batch processing and hyperplane splitting, as well as an enhancement to the projection step inspired by the work of Charles Holloway. We performed a study of 2-dimensional convex hull algorithms, concentrating on the Gift-Wrapping method, the Fast Hull method, and our own contribution, the Revised Gift-Wrapping method (a synthesis of the Gift-Wrapping method and the Fast Hull method). We also developed a Dikin's-type specialized quadratic programming projection algorithm as an alternative projection technique. Using only individual enhancements to the Dula and Helgason algorithm gave mixed results for small test data sets, but for large test data sets, individual enhancements were more likely to improve extreme point identification speed. Using all enhancements in concert (a grand synthesis of our efforts) provided a significant improvement to extreme point identification speed. Some of these ideas may also prove to be useful enhancements when applied to related problems. |
