ON HELLYS THEOREM - ALGORITHMS AND EXTENSIONS

Authors
BRIEDEN A GRITZMANN P
Citation
A. Brieden et P. Gritzmann, ON HELLYS THEOREM - ALGORITHMS AND EXTENSIONS, Discrete & computational geometry, 17(4), 1997, pp. 393-410
Citations number
18
Categorie Soggetti
Computer Sciences, Special Topics","Mathematics, General","Computer Science Theory & Methods",Mathematics
Journal title
Discrete & computational geometry → ACNP
ISSN journal
01795376
Volume
17
Issue
4
Year of publication
1997
Pages
393 - 410
Database
ISI
SICI code
0179-5376(1997)17:4<393:OHT-AA>2.0.ZU;2-X
Abstract
This paper studies algorithmic Helly-type problems in the framework of the algorithmic theory of convex bodies developed by Grotschel, Lovas z, and Schrijver. Various oracle-polynomial-time algorithms are presen ted that are complemented by NP-hardness results for polytopes. In add ition, some new Helly-type theorems are derived.