Home Bookmarks Papers Blog

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
}


Last modified: Mon Oct 17 02:17:47 CDT 2016