Online point location in planar arrangements and its applications

Sariel Har-Peled, Micha Sharir

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms
Pages57-66
Number of pages10
StatePublished - Dec 1 2001
Event2001 Operating Section Proceedings, American Gas Association - Dallas, TX, United States
Duration: Apr 30 2001May 1 2001

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other2001 Operating Section Proceedings, American Gas Association
CountryUnited States
CityDallas, TX
Period4/30/015/1/01

Keywords

  • Algorithms
  • Design
  • Theory
  • Verification

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Online point location in planar arrangements and its applications'. Together they form a unique fingerprint.

  • Cite this

    Har-Peled, S., & Sharir, M. (2001). Online point location in planar arrangements and its applications. In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 57-66). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).