Helly-type theorems and Generalized Linear Programming |
| |
Authors: | N Amenta |
| |
Institution: | (1) Computer Science, University of California, 94720 Berkeley, CA, USA;(2) The Geometry Center, 55454 Minneapolis, MN, USA |
| |
Abstract: | Recent combinatorial algorithms for linear programming can also be applied to certain nonlinear 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 constraint set of every GLP problem. Given a familyH of sets with a Helly-type theorem, we give a paradigm for finding whether the intersection ofH 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 surprising property that the constraints are nonconvex or even disconnected. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|