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

Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Wednesday, January 2, 2013 - 10:08:08 AM
Last modification on : Tuesday, January 11, 2022 - 11:16:20 AM
Long-term archiving on: : Friday, March 31, 2017 - 9:52:07 PM


Files produced by the author(s)


  • HAL Id : hal-00769529, version 1



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



Record views


Files downloads