Computing a Face in an Arrangement of Line Segments and Related Problems
Report ID: TR-334-91Author: Chazelle, Bernard / Edelsbrunner, Herbert / Guibas, Leonidas / Sharir, Micha / Snoeyink, Jack
Date: 1991-06-00
Pages: 21
Download Formats: |PDF|
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.