Computing a face in an arrangement of line segments

Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, Jack Snoeyink

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

8 Scopus citations

Abstract

We present a randomized incremental algorithm for computing a single face in an arrangement of n line segments in the plane that is fairly simple to implement. The expected running time of the algorithm is O(n α(n) log n). The analysis of the algorithm uses a novel approach that generalizes and extends the Clarkson-Shor analysis technique [3].

Original languageEnglish (US)
Title of host publicationProceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
PublisherAssociation for Computing Machinery
Pages441-448
Number of pages8
ISBN (Print)0897913760
StatePublished - Mar 1 1991
Event2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991 - San Francisco, United States
Duration: Jan 28 1991Jan 30 1991

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
CountryUnited States
CitySan Francisco
Period1/28/911/30/91

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Computing a face in an arrangement of line segments'. Together they form a unique fingerprint.

  • Cite this

    Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M., & Snoeyink, J. (1991). Computing a face in an arrangement of line segments. In Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991 (pp. 441-448). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery.