You are not logged in to this journal. Log in

We present several variants of a new randomized incremental algorithm for computing a cutting in an arrangement of n lines in the plane. The algorithms produce cuttings whose expected size is O(r²), and the expected running time of the algorithms is O(nr). Both bounds are asymptotically optimal for 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 bound) that generates small cuttings whose size is guaranteed to be close to the best known upper bound of J. Matou{s}ek [Discrete Comput. Geom., 20 (1998), pp. 427--448].