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(r2), 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 close to the known upper bound of m-ocfcp-97.
The algorithms described in the paper were implemented, and the demo
program can be downloaded from here.