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

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/inria-00493046
Contributor : Pedro Machado Manhaes de Castro <>
Submitted on : Thursday, June 17, 2010 - 5:57:04 PM
Last modification on : Saturday, January 27, 2018 - 1:31:26 AM
Long-term archiving on : Monday, October 22, 2012 - 11:56:06 AM

File

RR.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00493046, version 1

Collections

Citation

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

Share

Metrics

Record views

314

Files downloads

174