On-line Point Location in Planar Arrangements and Its
Applications

S. Har-Peled and M. Sharir

Recently, Har-Peled presented
a new randomized technique for online construction of the zone of a
curve in a planar arrangement of arcs. In this paper, we present
several applications of this technique, which yield improved solutions
to a variety of problems. These applications include: (i) an efficient
mechanism for performing on-line point location queries in an
arrangement of arcs; (ii) an efficient algorithm for computing an
approximation to the minimum-weight Steiner tree of a set of points,
where the weight is the number of intersections between the tree edges
and a given collection of arcs; (iii) a subquadratic algorithm for
cutting a set of pseudo-parabolas into pseudo-segments;(iv) an
algorithm for cutting a set of line segments(`rods') in 3-space so as
to eliminate all cycles in the vertical depth order; and (v) a
near-optimal algorithm for reporting all bichromatic intersections
between a set R of red arcs and a set B of blue arcs,
where the unions of the arcs in each set are both connected.
PDF.
OLD
Postscript :
PDF

@string{DCG = "Discrete Comput. Geom."}
@article{hs-oplpa-01-dcg
, author = "S.~{Har-Peled} and M.~Sharir"
, title = "Online Point Location in Planar Arrangements and Its
Applications"
, journal = DCG
, year = 2001
, pages = "19--40"
, volume = 26
}