Skip to Main content Skip to Navigation

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

Cited literature [24 references]  Display  Hide  Download
Contributor : Olivier Devillers <>
Submitted on : Thursday, April 3, 2014 - 2:51:38 PM
Last modification on : Monday, December 14, 2020 - 5:16:20 PM
Long-term archiving on: : Monday, April 10, 2017 - 9:41:03 AM


Files produced by the author(s)


  • HAL Id : hal-00769529, version 2



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⟩



Record views


Files downloads