A cone can help you find your way in a Poisson Delaunay triangulation

Nicolas Broutin 1 Olivier Devillers 2 Ross Hemsley 2
2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : Walking strategies are a standard tool for point location in a triangulation of size n. Although often claimed to be Θ(√n ) under random distribution hypotheses, this conjecture has only been formally proved by Devroye, Lemaire, and Moreau [Comp Geom-Theor Appl, vol. 29, 2004], in the case of the so called straight walk which has the very specific property that deciding whether a given (Delaunay) triangle belongs to the walk may be determined without looking at the other sites. In this paper we analyze a different walking strategy that follows vertex neighbour relations to move towards the query. We call this walk cone vertex walk. We prove that cone vertex walk visits Θ(√n ) vertices and can be constructed in Θ(√n ) time. We provide explicit bounds on the hidden constants.
Document type :
Reports
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download


https://hal.inria.fr/hal-00769529
Contributor : Olivier Devillers <>
Submitted on : Thursday, April 3, 2014 - 2:51:38 PM
Last modification on : Friday, May 25, 2018 - 12:02:03 PM
Long-term archiving on : Monday, April 10, 2017 - 9:41:03 AM

Files

RR_new.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00769529, version 2

Collections

Citation

Nicolas Broutin, Olivier Devillers, Ross Hemsley. A cone can help you find your way in a Poisson Delaunay triangulation. [Research Report] RR-8194, INRIA. 2012. ⟨hal-00769529v2⟩

Share

Metrics

Record views

555

Files downloads

340