Taking a Walk in a Planar Arrangement
Home Bookmarks Papers Blog

Taking a Walk in a Planar Arrangement

Sariel Har-Peled


We present a new 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 crosses, where the curve is given in an online manner), and to compute a level in an arrangement, both in an output-sensitive manner. The expected running time of the algorithm is O(lt+2(m+n)logn), where m is the number of intersections between the walk and the given arcs.

No algorithm with similar performance is known for the general case of arcs. For the case of lines and segments, our algorithm improves the best known algorithm of [OvL81] by almost a logarithmic factor.

Postscript, PDF
Chapter in thesis
Program Source


@article{h-twpa-00,
  author =       {S.~Har-Peled},
  journal =      {SIAM J. Comput.},
  title =        {Taking a Walk in a Planar Arrangement},
  year =         2000,
  pages = "1341--1367",
  volume = 30,
  number = 4
}

You might be interested also in the followup paper: On-line Point Location in Planar Arrangements and Its Applications.
Last modified: Fri Nov 14 11:27:15 CST 2014