Search
Close this search box.

Landmarks Point Location

Abstract

Landmarks Point Location

We present an efficient algorithm for planar point location. In our Landmarks algorithm (a.k.a. Jump & Walk), special points, landmarks, are chosen in a preprocessing stage, their place in the arrangement is found, and they are inserted into a data-structure that enables efficient nearest-neighbor search. Given a query point, the nearest landmark is located and then the algorithm “walks” from the landmark to the query point. We have compared the performance of our Landmarks algorithm to various point-location algorithms implemented in CGAL: naive approach, a walk along a line strategy and a trapezoidal-decomposition based search structure. The current implementation addresses general arrangements of arbitrary planar curves, including arrangements of non-linear segments (e.g., conic arcs) and allows for degenerate input (for example, more than two curves intersecting in a single point, or overlapping curves). All calculations use exact number types and thus result in the correct point location The results indicate that the Landmarks approach is the most efficient when the overall cost of a query is taken into account, combining both preprocessing and query time. The simplicity of the algorithm enables an almost straightforward implementation and rather easy maintenance. The generic programming implementation allows versatility both in the selected type of landmarks, and in the choice of the nearest-neighbor search structure. The end result is a highly effective point-location algorithm for most practical purposes.

Links

  • Idit Haran and Dan Halperin
    An Experimental Study of Point Location in Planar Arrangements in CGAL
    ACM Journal of Experimental Algorithmics 13, 2008 [link] [bibtex]
    A preliminary version appeared in Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (Alenex), pages 16-25, Miami, Florida, January 2006 [link] [bibtex]
  • Idit Haran
    Efficient point location in general planar subdivisions using landmarks
    M.Sc. Thesis [pdf] [bibtex]

Contacts

Dan Halperin
Idit Haran

Yair Oz - Webcreator

Contact

Skip to content