On Helly's theorem: Algorithms and extensions

被引：1
作者：
Brieden, A
Gritzmann, P
机构：
[1] Fachbereich IV, Mathematik, Universität Trier
来源：
DISCRETE & COMPUTATIONAL GEOMETRY | 1997年 / 17卷 / 04期
关键词：
D O I：
10.1007/PL00009300
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
This paper studies algorithmic Helly-type problems in the framework of the algorithmic theory of convex bodies developed by Grotschel, Lovasz, and Schrijver. Various oracle-polynomial-time algorithms are presented that are complemented by NP-hardness results for polytopes. In addition, some new Helly-type theorems are derived.
引用
收藏
页码：393 / 410
页数：18
相关论文
共 18 条
[1]  
Amenta A. B., 1993, THESIS U CALIFORNIA
[2]  
[Anonymous], 1993, GEOMETRIC ALGORITHMS
[3]  
[Anonymous], 1970, CONVEXITY OPTIMIZATI
[4]   COMPUTATIONAL ASPECTS OF HELLYS THEOREM AND ITS RELATIVES [J].
AVIS, D ;
HOULE, ME .
INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 1995, 5 (04) :357-367
[5]  
BOEDLAENDER HL, 1990, COMBINATORICA, V10, P203
[6]  
Danzer Ludwig, 1963, P S PURE MATH, VVII, P101
[7]  
Eckhoff J., 1993, HDB CONVEX GEOMETRY, P389, DOI DOI 10.1016/B978-0-444-89596-7.50017-1
[8]   ON THE COMPLEXITY OF 4 POLYHEDRAL SET CONTAINMENT PROBLEMS [J].
FREUND, RM ;
ORLIN, JB .
MATHEMATICAL PROGRAMMING, 1985, 33 (02) :139-145
[9]   INNER AND OUTER J-RADII OF CONVEX-BODIES IN FINITE-DIMENSIONAL NORMED SPACES [J].
GRITZMANN, P ;
KLEE, V .
DISCRETE & COMPUTATIONAL GEOMETRY, 1992, 7 (03) :255-280
[10]   MINKOWSKI ADDITION OF POLYTOPES - COMPUTATIONAL-COMPLEXITY AND APPLICATIONS TO GROBNER BASES [J].
GRITZMANN, P ;
STURMFELS, B .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1993, 6 (02) :246-269
12