Skip to Main content Skip to Navigation

Walking Faster in a Triangulation

Pedro Machado Manhães de Castro 1 Olivier Devillers 1
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
Abstract : Point location in a triangulation is one of the most studied problems in computational geometry. For a single query, stochastic walk is a good practical strategy. In this work, we propose two approaches improving the performance of the stochastic walk. The first improvement is based on a relaxation of the exactness of the predicate, whereas the second is based on termination guessing.
Document type :
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download
Contributor : Pedro Machado Manhaes de Castro Connect in order to contact the contributor
Submitted on : Thursday, June 17, 2010 - 5:57:04 PM
Last modification on : Monday, December 14, 2020 - 4:46:30 PM
Long-term archiving on: : Monday, October 22, 2012 - 11:56:06 AM


Files produced by the author(s)


  • HAL Id : inria-00493046, version 1



Pedro Machado Manhães de Castro, Olivier Devillers. Walking Faster in a Triangulation. [Research Report] RR-7322, Inria. 2010, pp.15. ⟨inria-00493046⟩



Les métriques sont temporairement indisponibles