Constructing cuttings in theory and practice

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

Abstract

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
PublisherACM
Pages327-336
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

Other

OtherProceedings of the 1998 14th Annual Symposium on Computational Geometry
CityMinneapolis, MN, USA
Period6/7/986/10/98

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