Computing a Face in an Arrangement of Line Segments and Related Problems

Abstract:

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.