Self-Adapting Point Location - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2009

Self-Adapting Point Location

Pedro M. M. de Castro
  • Fonction : Auteur
  • PersonId : 855158
Olivier Devillers

Résumé

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.
Fichier principal
Vignette du fichier
RR-7132.pdf (5.72 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00438486 , version 1 (04-12-2009)
inria-00438486 , version 2 (15-03-2010)
inria-00438486 , version 3 (12-07-2010)

Identifiants

  • HAL Id : inria-00438486 , version 3

Citer

Pedro M. M. de Castro, Olivier Devillers. Self-Adapting Point Location. [Research Report] RR-7132, INRIA. 2009, pp.24. ⟨inria-00438486v3⟩
194 Consultations
171 Téléchargements

Partager

Gmail Facebook X LinkedIn More