Algorithms for computing extreme points of convex hulls and the euclidean facilities location problem

The problem of computing all the extreme points of the convex hull of a set of n given points in d-dimensional Euclidean space is transformed into a set of Phase$\sb-$I linear programming problems. Several fast expected time algorithms are designed and implemented. These include a linear expected time algorithm which first finds all the maximal points in linear expected time and then finds all the extreme points in poly-log time. We have also designed a practical heuristic algorithm for computing extreme points. This algorithm first finds a set of candidates for extreme points and then discards the candidates which are not extreme points. Computational results show that this is the most efficient algorithm. The algorithm is then modified to compute the convex layers and depth of a point in a set. Computational results on the Cray-2 and on the NCUBE are presented. A simple heuristic algorithm for computing the maxima of a set of n d-dimensional vectors drawn from a uniform distribution is designed and implemented. It is proved that the expected number of point comparisons required by this algorithm is n+o(n). For the Euclidean multifacility location (EMFL) problem, the convergence of two well known algorithms are settled. We disprove the convergence of the first algorithm for solving the EMFL problem proposed by Miehle (1958) by presenting two counterexamples for which Miehle's algorithm fails to converge to the optimal solution. We then prove that the Hyperboloid Approximation Procedure proposed by Eyster et al (1973) for solving the perturbed problem always converges to the unique optimal solution of the perturbed problem from any initial approximation point. A globally convergent algorithm for the EMFL problem is designed. Two parallel algorithms for solving the Euclidean single facility location problem are designed and implemented on the NCUBE/7 hypercube with 64 processors. Computational results with various distributions are reported.