On Helly's theorem: Algorithms and extensions
type: Item
instance of: scholarly article
title: On Helly's theorem: Algorithms and extensions
zbMATH Open document ID: 0884.52010
DOI: 10.1007/PL00009300
published in: Discrete \& Computational Geometry
publication date: 1998-04-01T00:00:00Z
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.
Mathematics Subject Classification ID: 52A35
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1016877
zbMATH Keywords: tractability
zbMATH Keywords: \({\mathcal H}\)-polytope
zbMATH Keywords: \({\mathcal K}\)-polytope
zbMATH Keywords: oracle-polynomial-time algorithm
author: Andreas Brieden
author: Peter Gritzmann
reviewed by: Semin Akdoǧan
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1016877