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

Publikation: Beitrag in Fachzeitschrift › Artikel › Begutachtung

1 Zitat (Scopus)

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.

Originalsprache	Englisch
Seiten (von - bis)	393-410
Seitenumfang	18
Fachzeitschrift	Discrete and Computational Geometry
Jahrgang	17
Ausgabenummer	4
DOIs	https://doi.org/10.1007/PL00009300
Publikationsstatus	Veröffentlicht - Juni 1997
Extern publiziert	Ja

Zugriff auf Dokument

10.1007/PL00009300

Andere Dateien und Links

Verknüpfung zur Publikation in Scopus

Dieses zitieren

@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

Zugriff auf Dokument

Andere Dateien und Links

Fingerprint

Dieses zitieren