Online Point Location in Planar Arrangements and Its Applications |
| |
Authors: | S. Har-Peled M. Sharir |
| |
Affiliation: | (1) Department of Computer Science, DCL 2111, University of Illinois, 1304 West Springfield Ave., Urbana, IL 61801, USA http://www.uiuc.edu/~sariel/ sariel@uiuc.edu , US;(2) School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel and Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA sharir@math.tau.ac.il, US |
| |
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. Received December 22, 1999, and in revised form August 25, 2000. Online publication May 11, 2001. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|