Home | Bookmarks | Papers | Blog |

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(l

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