On Helly's theorem: Algorithms and extensions (Q1356077): Difference between revisions

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.