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.