@inproceedings{2ea73005251c4bcd9a965c3e02abb791,
title = "Online point location in planar arrangements and its applications",
abstract = "Recently, Har-Peled [17] 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 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.",
keywords = "Algorithms, Design, Theory, Verification",
author = "Sariel Har-Peled and Micha Sharir",
year = "2001",
language = "English (US)",
isbn = "0898714907",
series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
pages = "57--66",
booktitle = "Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms",
note = "2001 Operating Section Proceedings, American Gas Association ; Conference date: 30-04-2001 Through 01-05-2001",
}