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.
@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
}