Abstract
Recently, Har-Peled [HP2] 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 online 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 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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 19-40 |
| Number of pages | 22 |
| Journal | Discrete and Computational Geometry |
| Volume | 26 |
| Issue number | 1 |
| DOIs | |
| State | Published - Jul 2001 |
ASJC Scopus subject areas
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics