Self-Adapting Point Location - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2009

Self-Adapting Point Location

(1) , (1)
1
Pedro M. M. de Castro
  • Function : Author
  • PersonId : 855158
Olivier Devillers

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.
Fichier principal
Vignette du fichier
RR-7132.pdf (5.72 Mo) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

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

Identifiers

  • HAL Id : inria-00438486 , version 3

Cite

Pedro M. M. de Castro, Olivier Devillers. Self-Adapting Point Location. [Research Report] RR-7132, INRIA. 2009, pp.24. ⟨inria-00438486v3⟩
186 View
160 Download

Share

Gmail Facebook Twitter LinkedIn More