THE COMPLEXITY AND CONSTRUCTION OF MANY FACES IN ARRANGEMENTS OF LINES AND OF SEGMENTS

被引:61
作者
EDELSBRUNNER, H
GUIBAS, LJ
SHARIR, M
机构
[1] STANFORD UNIV,DEPT COMP SCI,STANFORD,CA 94305
[2] NYU,COURANT INST MATH SCI,NEW YORK,NY 10012
[3] DEC SYST RES CTR,PALO ALTO,CA 94301
[4] TEL AVIV UNIV,SCH MATH SCI,IL-69978 TEL AVIV,ISRAEL
关键词
D O I
10.1007/BF02187784
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We show that the total number of edges of m faces of an arrangement of n lines in the plane is O(m2/3-δn2/3+2 δ+n) for any δ>0. The proof takes an algorithmic approach, that is, we describe an algorithm for the calculation of these m faces and derive the upper bound from the analysis of the algorithm. The algorithm uses randomization and its expected time complexity is O(m2/3-δn2/3+2 δ log n+n log n log m). If instead of lines we have an arrangement of n line segments, then the maximum number of edges of m faces is O(m2/3-δn2/3+2 δ+nα (n) log m) for any δ>0, where α(n) is the functional inverse of Ackermann's function. We give a (randomized) algorithm that produces these faces and takes expected time O(m2/3-δn2/3+2 δ log+nα(n) log2n log m). © 1990 Springer-Verlag New York Inc.
引用
收藏
页码:161 / 196
页数:36
相关论文
共 29 条
[1]  
AGARWAL PK, 1989, 5TH P ACM S COMP GEO, P11
[2]  
[Anonymous], 1987, EATCS MONOGRAPHS THE
[3]  
ARONOV B, 1989, UIUCDCSR-891527 U IL
[4]  
BENTLEY JL, 1979, IEEE T COMPUT, V28, P643, DOI 10.1109/TC.1979.1675432
[5]   INTERSECTION OF CONVEX OBJECTS IN 2-DIMENSION AND 3-DIMENSION [J].
CHAZELLE, B ;
DOBKIN, DP .
JOURNAL OF THE ACM, 1987, 34 (01) :1-27
[6]   NEW APPLICATIONS OF RANDOM SAMPLING IN COMPUTATIONAL GEOMETRY [J].
CLARKSON, KL .
DISCRETE & COMPUTATIONAL GEOMETRY, 1987, 2 (02) :195-222
[7]   COMBINATORIAL COMPLEXITY-BOUNDS FOR ARRANGEMENTS OF CURVES AND SPHERES [J].
CLARKSON, KL ;
EDELSBRUNNER, H ;
GUIBAS, LJ ;
SHARIR, M ;
WELZL, E .
DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (02) :99-160
[8]   ON K-HULLS AND RELATED PROBLEMS [J].
COLE, R ;
SHARIR, M ;
YAP, CK .
SIAM JOURNAL ON COMPUTING, 1987, 16 (01) :61-77
[9]   ON THE MAXIMAL NUMBER OF EDGES OF MANY FACES IN AN ARRANGEMENT [J].
EDELSBRUNNER, H ;
WELZL, E .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 1986, 41 (02) :159-166
[10]   CONSTRUCTING ARRANGEMENTS OF LINES AND HYPERPLANES WITH APPLICATIONS [J].
EDELSBRUNNER, H ;
OROURKE, J ;
SEIDEL, R .
SIAM JOURNAL ON COMPUTING, 1986, 15 (02) :341-363