Login
- Title:
On Helly's theorem: Algorithms and extensions
- Document type:
- Zeitschriftenaufsatz
- Author(s):
- Brieden, A. and P. Gritzmann
- Abstract:
- This paper studies algorithmic Helly-type problems in the framework of the algorithmic theory of convex bodies developed by Grötschel, Lovász, and Schrijver. Various oracle-polynomial-time algorithms are presented that are complemented by NP-hardness results for polytopes. In addition, some new Helly-type theorems are derived.
- Journal title:
- Discrete & Computational Geometry
- Year:
- 1997
- Journal issue:
- 17
- Pages contribution:
- 393-410
- Reviewed:
- ja
- Language:
- en
- TUM Institution:
- Lehrstuhl für Angewandte Geometrie und Diskrete Mathematik
BibTeX