Self-Adapting Point Location

Pedro De Castro 1 Olivier Devillers 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : Point location in spatial subdivision is one of the most studied problems in computational geometry. In the case of triangulations of Rd, we revisit the problem to exploit a possible coherence between the query-points. For a single query, walking in the triangulation is a classical strategy with good practical behavior and expected complexity O(n^(1/d)) if the points are evenly distributed. For a batch of query-points, the main idea is to use previous queries to improve the current one; we compare various strategies that have an influence on the constant hidden in the big-O notation. Still regarding the complexity of a query, 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 #(.) indicates the number of simplices crossed by the line pq, and p is a previously located query. The data structure has O(n log n) construction complexity and O(n) memory complexity.
Type de document :
[Research Report] RR-7132, INRIA. 2009, pp.24
Liste complète des métadonnées
Contributeur : Olivier Devillers <>
Soumis le : lundi 12 juillet 2010 - 13:07:47
Dernière modification le : samedi 27 janvier 2018 - 01:31:24
Document(s) archivé(s) le : jeudi 1 décembre 2016 - 16:39:22


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00438486, version 3



Pedro De Castro, Olivier Devillers. Self-Adapting Point Location. [Research Report] RR-7132, INRIA. 2009, pp.24. 〈inria-00438486v3〉



Consultations de la notice


Téléchargements de fichiers