Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

Report ID:

TR-334-91

Authors:

Chazelle, Bernard [1] / Edelsbrunner, Herbert [2] / Guibas, Leonidas [3] / Sharir, Micha [4] / Snoeyink, Jack [5]

Date:

May 1991

Pages:

21

Download Formats:

[PDF [6]]

We present 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. We also present 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.

- This technical report has been published as
- Computing a Face in an Arrangement of Line Segments and Related

Problems. Bernard Chazelle, Herbert Edelsbrunner,

Leonidas Guibas, Micha Sharir, and Jack Snoeyink,SIAM Journal on Computing,22(6),

1993, pp. 1286-1302.

**Links**

[1] http://www.cs.princeton.edu/research/techreps/author/283

[2] http://www.cs.princeton.edu/research/techreps/author/404

[3] http://www.cs.princeton.edu/research/techreps/author/417

[4] http://www.cs.princeton.edu/research/techreps/author/461

[5] http://www.cs.princeton.edu/research/techreps/author/466

[6] ftp://ftp.cs.princeton.edu/techreports/1991/334.pdf