On Helly's theorem: Algorithms and extensions

A. Brieden; P. Gritzmann

doi:10.1007/PL00009300

On Helly's theorem: Algorithms and extensions

A. Brieden, P. Gritzmann

University of Trier

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

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 ℕℙ-hardness results for polytopes. In addition, some new Helly-type theorems are derived.

Original language	English
Pages (from-to)	393-410
Number of pages	18
Journal	Discrete and Computational Geometry
Volume	17
Issue number	4
DOIs	https://doi.org/10.1007/PL00009300
State	Published - Jun 1997
Externally published	Yes

Access to Document

10.1007/PL00009300

Cite this

@article{7bccfdb5a966460b869c57545801e416,

title = "On Helly's theorem: Algorithms and extensions",

abstract = "This paper studies algorithmic Helly-type problems in the framework of the algorithmic theory of convex bodies developed by Gr{\"o}tschel, Lov{\'a}sz, and Schrijver. Various oracle-polynomial-time algorithms are presented that are complemented by ℕℙ-hardness results for polytopes. In addition, some new Helly-type theorems are derived.",

author = "A. Brieden and P. Gritzmann",

year = "1997",

month = jun,

doi = "10.1007/PL00009300",

language = "English",

volume = "17",

pages = "393--410",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - On Helly's theorem

T2 - Algorithms and extensions

AU - Brieden, A.

AU - Gritzmann, P.

PY - 1997/6

Y1 - 1997/6

N2 - 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 ℕℙ-hardness results for polytopes. In addition, some new Helly-type theorems are derived.

AB - 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 ℕℙ-hardness results for polytopes. In addition, some new Helly-type theorems are derived.

UR - http://www.scopus.com/inward/record.url?scp=0031525872&partnerID=8YFLogxK

U2 - 10.1007/PL00009300

DO - 10.1007/PL00009300

M3 - Article

AN - SCOPUS:0031525872

SN - 0179-5376

VL - 17

SP - 393

EP - 410

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 4

ER -

On Helly's theorem: Algorithms and extensions

Abstract

Access to Document

Other files and links

Fingerprint

Cite this