Constructing cuttings in theory and practice

Research output: Contribution to conferencePaperpeer-review


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 dose to the known upper bound of [9].

Original languageEnglish (US)
Number of pages10
StatePublished - 1998
Externally publishedYes
EventProceedings of the 1998 14th Annual Symposium on Computational Geometry - Minneapolis, MN, USA
Duration: Jun 7 1998Jun 10 1998


OtherProceedings of the 1998 14th Annual Symposium on Computational Geometry
CityMinneapolis, MN, USA

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


Dive into the research topics of 'Constructing cuttings in theory and practice'. Together they form a unique fingerprint.

Cite this