Computing many faces in arrangements of lines and segments

被引：28

作者：

Agarwal, PK

Matousek, J

Schwarzkopf, O

机构：

[1] Duke Univ, Dept Comp Sci, Durham, NC 27708 USA

[2] Charles Univ, Dept Appl Math, CR-11800 Prague, Czech Republic

[3] Univ Utrecht, Dept Comp Sci, NL-3508 TB Utrecht, Netherlands

来源：

SIAM JOURNAL ON COMPUTING | 1998年 / 27卷 / 02期

关键词：

arrangements; random sampling; duality;

D O I：

10.1137/S009753979426616X

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously known ones. pn The main new idea is a simple randomized O(n log n) expected time algorithm for computing root n cells in an arrangement of n lines.

引用

收藏

页码：491 / 505

页数：15

相关论文

共 21 条

[1] PARTITIONING ARRANGEMENTS OF LINES .2. APPLICATIONS [J].

AGARWAL, PK .

DISCRETE & COMPUTATIONAL GEOMETRY, 1990, 5 (06) :533-573

[2]

[Anonymous], ISRAEL J MATH

[3] THE NUMBER OF EDGES OF MANY FACES IN A LINE SEGMENT ARRANGEMENT [J].

ARONOV, B ;

EDELSBRUNNER, H ;

GUIBAS, LJ ;

SHARIR, M .

COMBINATORICA, 1992, 12 (03) :261-274

[4] A DETERMINISTIC VIEW OF RANDOM SAMPLING AND ITS USE IN GEOMETRY [J].

CHAZELLE, B ;

FRIEDMAN, J .

COMBINATORICA, 1990, 10 (03) :229-249

[5] COMPUTING A FACE IN AN ARRANGEMENT OF LINE SEGMENTS AND RELATED PROBLEMS [J].

CHAZELLE, B ;

EDELSBRUNNER, H ;

GUIBAS, L ;

SHARIR, M ;

SNOEYINK, J .

SIAM JOURNAL ON COMPUTING, 1993, 22 (06) :1286-1302

[6] RAY SHOOTING IN POLYGONS USING GEODESIC TRIANGULATIONS [J].

CHAZELLE, B ;

EDELSBRUNNER, H ;

GRIGNI, M ;

GUIBAS, L ;

HERSHBERGER, J ;

SHARIR, M ;

SNOEYINK, J .

ALGORITHMICA, 1994, 12 (01) :54-68

[7]

CLARKSON K, 1990, UNPUB COMPUTING SING

[8] 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

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

CLARKSON, KL ;

SHOR, PW .

DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (05) :387-421

[10] ON LAZY RANDOMIZED INCREMENTAL CONSTRUCTION [J].

DEBERG, M ;

DOBRINDT, K ;

SCHWARZKOPF, O .

DISCRETE & COMPUTATIONAL GEOMETRY, 1995, 14 (03) :261-286