Schreiber Building
Computational Geometry Seminar
Wednesday, May 24th, 2006, 16:10-18:00
Room 309
Schreiber Building
We will discuss the performance in practice of various point-location algorithms implemented in CGAL. We will elaborate on a newly devised Landmarks algorithm.
This is joint work with Dan Halperin
Other algorithms that will be presented are: a 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.
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 report on extensive experiments with arrangements composed of line segments or conic arcs. 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.