Personal tools
You are here: Home Projects Internal Projects Landmarks Point Location
« April 2017 »
April
SuMoTuWeThFrSa
1
2345678
9101112131415
16171819202122
23242526272829
30
Log in


Forgot your password?
 

Landmarks Point Location

[Landmarks Point Location]

Abstract

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]

Contact

Dan Halperin http://acg.cs.tau.ac.il/danhalperin danha@post.tau.ac.il
Idit Haran http://www.cs.tau.ac.il/~haranidi haranidi@post.tau.ac.il
Document Actions