COMPUTING A FACE IN AN ARRANGEMENT OF LINE SEGMENTS AND RELATED PROBLEMS

被引：27

作者：

CHAZELLE, B

EDELSBRUNNER, H

GUIBAS, L

SHARIR, M

SNOEYINK, J

机构：

[1] UNIV ILLINOIS,DEPT COMP SCI,URBANA,IL 61801

[2] DIGITAL EQUIPMENT CORP,DEC SYST RES CTR,PALO ALTO,CA 94301

[3] MIT,COMP SCI LAB,CAMBRIDGE,MA 02139

[4] STANFORD UNIV,DEPT COMP SCI,STANFORD,CA 94305

[5] TEL AVIV UNIV,SCH MATH SCI,IL-69978 TEL AVIV,ISRAEL

[6] NYU,COURANT INST MATH SCI,NEW YORK,NY 10012

来源：

SIAM JOURNAL ON COMPUTING | 1993年 / 22卷 / 06期

关键词：

COMPUTATIONAL GEOMETRY; ARRANGEMENTS; RANDOMIZED INCREMENTAL ALGORITHMS; PROBABILISTIC BACKWARDS ANALYSIS; DAVENPORT-SCHINZEL SEQUENCES;

D O I：

10.1137/0222077

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper presents a randomized incremental algorithm for computing a single face in an arrangement of n line segments in the plane that is fairly simple to implement. The expected running time of the algorithm is O(n alpha(n)log n). The analysis of the algorithm uses a novel approach that generalizes and extends the Clarkson-Shor analysis technique [in Discrete Comput.Geom.,4 (1989), pp. 387-421]. A few extensions of the technique, obtaining efficient randomized incremental algorithms for constructing the entire arrangement of a collection of line segments and for computing a single face in an arrangement of Jordan arcs are also presented.

引用

页码：1286 / 1302

页数：17

共 20 条

[11]

MEHLHORN K, 1990, UNPUB

[12]

MILLER N, 1991, UNPUB EFFICIENT RAND

[13]

MITCHELL JSB, 1990, UNPUB COMPUTING SING

[14] A FAST PLANAR PARTITION ALGORITHM .1. [J].