CGAL homepage   ACG at TAU  
TAU Members   People   Projects  

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

Contact

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

[Projects Page] [Top]
Site is maintained by Efi Fogel. Last modified: May 14 2006.