Constructing cuttings in theory and practice

We present a new randomized incremental algorithm for computing a cutting in an arrangement of lines in the plane. The algorithm produce cuttings whose expected size is O(r²), and the expected running time of the algorithm is O(nr). 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 also present another efficient algorithm (with slightly worse time bound) that generates small cuttings whose size is guaranteed to be dose to the known upper bound of [9].