Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00438486
Contributor : Olivier Devillers <>
Submitted on : Friday, December 4, 2009 - 10:11:42 AM
Last modification on : Monday, December 14, 2020 - 4:46:30 PM
Long-term archiving on: : Thursday, October 18, 2012 - 9:50:09 AM

File

RR-7132.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00438486, version 1

Collections

Citation

Pedro de Castro, Olivier Devillers. Self-Adapting Point Location. [Research Report] RR-7132, 2009, pp.24. ⟨inria-00438486v1⟩

Share

Metrics

Record views

8

Files downloads

7