Skip to Main content Skip to Navigation

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.
Document type :
Complete list of metadata
Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Monday, July 12, 2010 - 1:07:47 PM
Last modification on : Monday, December 14, 2020 - 4:46:30 PM
Long-term archiving on: : Thursday, December 1, 2016 - 4:39:22 PM


Files produced by the author(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⟩



Les métriques sont temporairement indisponibles