Simple and Efficient Distribution-Sensitive Point Location in Triangulations

Pedro Machado Manhães de Castro 1 Olivier Devillers 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : 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 hypothe- ses these complexities generalize to any finite dimension. Fi- nally, 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 knowl- edge, Keep, Jump, & Climb is the first practical distribution- sensitive algorithm that works both in theory and in practice for Delaunay triangulations.
Type de document :
Communication dans un congrès
Thirteenth Workshop on Algorithm Engineering and Experiments, 2011, San Francisco, United States. SIAM, pp.127-138, 2011, 〈http://www.siam.org/proceedings/alenex/2011/alx11_13_decastrop.pdf〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00850559
Contributeur : Olivier Devillers <>
Soumis le : mercredi 7 août 2013 - 11:51:45
Dernière modification le : samedi 27 janvier 2018 - 01:31:24

Identifiants

  • HAL Id : hal-00850559, version 1

Collections

Citation

Pedro Machado Manhães de Castro, Olivier Devillers. Simple and Efficient Distribution-Sensitive Point Location in Triangulations. Thirteenth Workshop on Algorithm Engineering and Experiments, 2011, San Francisco, United States. SIAM, pp.127-138, 2011, 〈http://www.siam.org/proceedings/alenex/2011/alx11_13_decastrop.pdf〉. 〈hal-00850559〉

Partager

Métriques

Consultations de la notice

149