HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 metadata

Cited literature [24 references]  Display  Hide  Download

Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Thursday, April 3, 2014 - 2:51:38 PM
Last modification on : Friday, January 21, 2022 - 3:18:16 AM
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