| HAL-Inria | Publications, software ... of Inria's scientists |
Reports
Self-Adapting Point Location
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.
https://hal.inria.fr/inria-00438486
Contributor : Olivier Devillers <>
Submitted on : Monday, July 12, 2010 - 1:07:47 PM
Last modification on : Tuesday, December 3, 2019 - 4:26:47 PM
Document(s) archivé(s) le : Thursday, December 1, 2016 - 4:39:22 PM
Contributor : Olivier Devillers <>
Submitted on : Monday, July 12, 2010 - 1:07:47 PM
Last modification on : Tuesday, December 3, 2019 - 4:26:47 PM
Document(s) archivé(s) le : Thursday, December 1, 2016 - 4:39:22 PM
File
RR-7132.pdf
Files produced by the author(s)