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 \({\Bbb N \Bbb P}\) -hardness results for polytopes. In addition, some new Helly-type theorems are derived.
Article PDF
Similar content being viewed by others
Use our pre-submission checklist
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received June 15, 1996, and in revised form August 16, 1996.
Rights and permissions
About this article
Cite this article
Brieden, A., Gritzmann, P. On Helly's Theorem: Algorithms and Extensions . Discrete Comput Geom 17, 393–410 (1997). https://doi.org/10.1007/PL00009300
Issue Date:
DOI: https://doi.org/10.1007/PL00009300