Simple and Efficient Distribution-Sensitive Point Location in Triangulations

We analyze, implement, and evaluate a distribution-sensitive point location algorithm based on the classical Jump & Walk, called Keep, Jump, & Walk. For a batch of query points, the main idea is to use previous queries to improve the current one. In practice, Keep, Jump, & Walk is actually a very competitive method to locate points in a triangulation. Regarding point location in a Delaunay triangulation, we show how the Delaunay hierarchy can be used to answer, under some hypotheses, a query q with a O(log#(pq)) randomized expected complexity, where p is a previously located query and #(s) indicates the number of simplices crossed by the line segment s. The Delaunay hierarchy has O(n log n) time complexity and O(n) memory complexity in the plane, and under certain realistic hypotheses these complexities generalize to any finite dimension. Finally, we combine the good distribution-sensitive behavior of Keep, Jump, & Walk, and the good complexity of the Delaunay hierarchy, into a novel point location algorithm called Keep, Jump, & Climb. To the best of our knowledge, Keep, Jump, & Climb is the first practical distribution-sensitive algorithm that works both in theory and in practice for Delaunay triangulations.

The paper has been presented at ALENEX’11, and published in the Workshop on Algorithm Engineering and Experiments, pages 127-138, 2011, and can be found here. We also have produced a JavaScript program demonstrating some of these strategies, see here; this program has been presented as a demo at SoCG’11, and can be found in Proceedings of 27th Annual Symposium on Computational Geometry, pages 295-296, 2011. A journal version of this paper was published in CAGD that you can find here.

Open full-size figure