Login
TitleHelly Theorems and Generalized Linear Programming (Article)
inDiscrete and Computational Geometry
Author(s) Nina Amenta
Year 1994
Volume12
Number3
Pages241--261
Download
BibTeX
Abstract Recent combinatorial algorithms for linear programming can also be applied to certain non-linear problems. We call these Generalized Linear Programming, or GLP, problems. We connect this class to a collection of results from combinatorial geometry called Helly-type theorems. We show that there is a Helly-type theorem about the constrainst set of every GLP problem. Given a family H of sets with a Helly-type theorem, we give a paradigm for finding whether the intersection of H is empty, by formulating the question as a GLP problem. This leads to many applications, including linear expected time algorithms for finding line transversals and mini-max hyperplane fitting. Our applications include GLP problems with the suprising property that the constraints are non-convex or even disconnected.
Note An earlier version appeared in the Proceedings of the 9th Annual ACM Syposium on Computational Geometry, (1993) pages 63-72