FINDING STABBING LINES IN 3-SPACE

被引：16

作者：

PELLEGRINI, M ^{[1
]}

SHOR, PW ^{[1
]}

机构：

[1] AT&T BELL LABS,MURRAY HILL,NJ 07974

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 1992年 / 8卷 / 02期

关键词：

D O I：

10.1007/BF02293043

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A line intersecting all polyhedra in a set B is called a "stabber" for the set B. This paper addresses some combinatorial and algorithmic questions about the set J(B) of all lines stabbing B. We prove that the combinatorial complexity of J(B) has an O(n(3)2c square-root log n) upper bound, where n is the total number of facets in B, and c is a suitable constant. This bound is almost tight. Within the same time bound it is possible to determine if a stabbing line exists and to find one.

引用

页码：191 / 208

页数：18

共 22 条

[1]

AGARWAL PK, 1989, 5TH P ACM S COMP GEO, P11

[2]

AMENTA A, 1991, IN PRESS 3RD P ACM S

[3]

[Anonymous], 1987, EATCS MONOGRAPHS THE

[4] LOWER BOUNDS FOR LINE STABBING [J].

AVIS, D ;

ROBERT, JM ;

WENGER, R .

INFORMATION PROCESSING LETTERS, 1989, 33 (02) :59-62

[5] POLYHEDRAL LINE TRANSVERSALS IN SPACE [J].

AVIS, D ;

WENGER, R .

DISCRETE & COMPUTATIONAL GEOMETRY, 1988, 3 (03) :257-265

[6]

AVIS D, 1987, 3RD P ACM S COMP GEO, P300

[7]

BORSUK K, 1969, MULTIDIMENSIONAL ANA

[8]

CHAZELLE B, 1990, UIUCDCSR901569 U ILL

[9] NEW APPLICATIONS OF RANDOM SAMPLING IN COMPUTATIONAL GEOMETRY [J].

CLARKSON, KL .

DISCRETE & COMPUTATIONAL GEOMETRY, 1987, 2 (02) :195-222

[10]

EDELSBRUNNER H, 1987, MAXIMUM NUMBER WAYS

← 1 2 3 →