Constructing cuttings in theory and practice

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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)
Title of host publicationProceedings of the Annual Symposium on Computational Geometry
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

  • Chemical Health and Safety
  • Software
  • Safety, Risk, Reliability and Quality
  • Geometry and Topology

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

Cite this