Computing Cuttings in Practice

Constructing Cuttings in Theory and Practice

Sariel Har-Peled

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 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.

Appeared in the 14th ACM Symp. of Comput. Geom., 1998

Postscript file
Demo program

@article{h-cctp-00
, author =      "S. Har-Peled"
, title =       "Constructing planar cuttings in theory and practice"
, year =        2000
, journal =     {SIAM J. Comput.}
, pages =       "2016--2039"
, volume =      29
, number =      6
}

Last updated: Sun Feb 25 15:01:41 CST 2001