Skip to main content
eScholarship
Open Access Publications from the University of California

Helly Theorems and Generalized Linear Programming

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.

Main Content
Current View