Taking a walk in a planar arrangement

Research output: Contribution to journalArticlepeer-review

Abstract

We present a randomized algorithm for computing portions of an arrangement of n arcs in the plane, each pair of which intersect in at most t points. We use this algorithm to perform online walks inside such an arrangement (i.e., compute all the faces that a curve, given in an online manner, crosses) and to compute a level in an arrangement, both in an output-sensitive manner. The expected running time of the algorithm is O(λt+2(m + n) log n), where m is the number of intersections between the walk and the given arcs. No similarly efficient algorithm is known for the general case of arcs. For the case of lines and for certain restricted cases involving line segments, our algorithm improves the best known algorithm of [M. H. Overmars and J. van Leeuwen, J. Comput. System Sci., 23 (1981), pp. 166-204] by almost a logarithmic factor.

Original languageEnglish (US)
Pages (from-to)1341-1367
Number of pages27
JournalSIAM Journal on Computing
Volume30
Issue number4
DOIs
StatePublished - 2000

Keywords

  • Computational geometry
  • Levels
  • Planar arrangements
  • Single face

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Taking a walk in a planar arrangement'. Together they form a unique fingerprint.

Cite this