On Helly's theorem: Algorithms and extensions

DOI10.1007/PL00009300MaRDI QIDQ1356077zbMATH OpenFDO

Authors Andreas Brieden, Peter Gritzmann

Publication date 1 April 1998

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/PL00009300

zbMATH Keywords

\({\mathcal H}\)-polytope\({\mathcal K}\)-polytopeoracle-polynomial-time algorithmtractability

Mathematics Subject Classification ID

Helly-type theorems and geometric transversal theory (52A35) Analysis of algorithms and problem complexity (68Q25)

Review text

In the realm of the algorithmic theory of convex bodies, algorithmic aspects of various geometric Helly-type problems for polytopes and convex bodies are studied, with emphasis on the latter. The authors use the oracle-polynomial-time algorithm introduced by \textit{M. Grötschel}, \textit{L. Lovász} and \textit{A. Schrijver} in `Geometric algorithms and computational optimization' (Springer) (1988; Zbl 0634.05001) and (1993; Zbl 0837.05001). Starting from Helly's theorem, they define the Weak, the Weak Fat and Strong Fat Helly problem, and show that the Weak Helly problem is algorithmically tractable. Tractability results are then given in the following theorems: Theorem 1: The Weak Helly problem can be solved in oracle polynomial time. Theorem 2: The Weak Fat Helly problem can be solved in oracle polynomial time. In a third theorem the complexity status of the strong fat Helly problem for \({\mathcal V}\)- and \({\mathcal H}\)-polytopes is examined; Finally several new Helly-type theorems dealing with the shape of intersections are given.

Recommendations

• COMPUTATIONAL ASPECTS OF HELLY’S THEOREM AND ITS RELATIVES
• Helly-type theorems and generalized linear programming
• Helly’s theorem: New variations and applications

Cited in

(10)

• On Gurevich's theorem on sequential algorithms
• scientific article; zbMATH DE number 5130830 (Why is no real title available?)
• Some computational aspects of geodesic convex sets in a simple polygon
• On the Algorithmic Aspects of Discrete and Lexicographic Helly-Type Theorems and the Discrete LP-Type Model
• Some computational aspects of Helly-type theorems
• scientific article; zbMATH DE number 18886 (Why is no real title available?)
• Deterministic and randomized polynomial‐time approximation of radii
• COMPUTATIONAL ASPECTS OF HELLY’S THEOREM AND ITS RELATIVES
• Helly-type theorems in property testing
• scientific article; zbMATH DE number 7651162 (Why is no real title available?)

This page was built for publication: On Helly's theorem: Algorithms and extensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1356077)