HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Practical Distribution-Sensitive Point Location in Triangulations

Pedro Machado Manhães de Castro 1 Olivier Devillers 2
2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : We design, 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 ac- tually a very competitive method to locate points in a triangulation. We also study some constant- memory distribution-sensitive point location algorithms, which work well in practice with the classical space-filling heuristic for fast point location. 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(nlogn) time complexity and O(n) memory complexity in the plane, and under certain realistic hypotheses these com- plexities 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [44 references]  Display  Hide  Download

Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Thursday, March 21, 2013 - 9:56:13 AM
Last modification on : Wednesday, February 2, 2022 - 3:55:41 PM
Long-term archiving on: : Sunday, April 2, 2017 - 4:20:17 PM


Files produced by the author(s)




Pedro Machado Manhães de Castro, Olivier Devillers. Practical Distribution-Sensitive Point Location in Triangulations. Computer Aided Geometric Design, Elsevier, 2013, 30, pp.431-450. ⟨10.1016/j.cagd.2013.02.004⟩. ⟨hal-00803093⟩



Record views


Files downloads