Constructing cuttings in theory and practice
Sariel Har-Peled · 1998
We present a new randomized incremental algorithm for computing a cutting in an arrangement of lines in the plane.The nlgorithm produce cuttings whose expected size is 0 P"), and the expected running time of the algorithm is 0 I r-w).Both bounds are asymptotically optimal for nondegenerate arrangements.The algorithm is also simple to implement, and we present empirical results showing that the algorithm and some of its variants perform well in practice.We alao present another efficient algorithm (with slightly worse time bound) that generates small cuttings whose size is guaranteed to be close to the known upper bound of [9].