Helly theorems and generalized linear programming

Abstract

This thesis establishes a connection between the Helly theorems, a collection of results from combinatorial geometry, and the class of problems which we call Generalized Linear Programming, or GLP, which can be solved by combinatorial linear programming algorithms like the simplex method. We use these results to explore the class GLP and show new applications to geometric optimization, and also to prove Helly theorems. In general, a GLP is a set of constraints and a function to be minimized, which obey certain combinatorial conditions. Linear programming is an example. A Helly theorem is also defined by its combinatorial structure. We observe that there is a Helly theorem about any GLP, which is that the minimum is no greater than m if and only if the minimum of every subproblem with d + 1 constraints is no greater than m. We use this observation to prove Helly theorems. Then we give a paradigm which usually allows us to construct a GLP corresponding to a given Helly theorem. Most of our algorithmic results are based on this paradigm. We show that in there are GLPs in which the constraints or objective function are not only non-linear but also non-convex or disconnected. We give numerous applications, concentrating on expected O(n) time algorithms. Some examples are that the largest axis-aligned box in the the intersection of a family of convex sets in fixed dimension, and the translation and scaling which minimizes the Hausdorff distance between two convex polygons in the plane, can be found by GLP. An example of a second family of results is a GLP to find the smallest factor by which a family of boxes can be scaled around their centers so as to admit a hyperplane transversal, thus fitting a hyperplane to the family of centers. The author was supported by an National Science Foundation Graduate Fellowship, an AT&T Graduate Research Program for Women Grant, and a U.C. President's Dissertation Year Fellowship. Some of this work was done while visiting AT&T Bell Labs at Murry Hill and the Freie Universiatat, Berlin.