Constructing planar cuttings in theory and practice

We present several variants of a new randomized incremental algorithm for c omputing a cutting in an arrangement of n lines in the plane. The algorithm s produce cuttings whose expected size is O(r(2)), and the expected running time of the algorithms is O(nr). Both bounds are asymptotically optimal fo r nondegenerate arrangements. The algorithms are also simple to implement, and we present empirical results showing that they perform well in practice . We also present another efficient algorithm (with slightly worse time bou nd) that generates small cuttings whose size is guaranteed to be close to t he best known upper bound of J. Matousek [Discrete Comput. Geom., 20 (1998) , pp. 427-448].