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

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.