Computing a face in an arrangement of line segments and related problems

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

Research output: Contribution to journalArticle

31 Scopus citations

Abstract

This paper presents 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 [in Discrete Comput. Geom., 4(1989), pp. 387-421]. A few extensions of the technique, obtaining efficient randomized incremental algorithms for constructing the entire arrangement of a collection of line segments and for computing a single face in an arrangement of Jordan arcs are also presented.

Original languageEnglish (US)
Pages (from-to)1286-1302
Number of pages17
JournalSIAM Journal on Computing
Volume22
Issue number6
DOIs
StatePublished - Jan 1 1993

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

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

  • Cite this