Walking Faster in a Triangulation - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2010

Walking Faster in a Triangulation

(1) , (1)
1

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.
La localisation d'un point dans une triangulation est un des problèmes les plus étudiés en géométrie algorithmique. Pour un petit nombre de requêtes, la marche stochastique est une bonne stratégie en pratique. Dans ce travail, nous proposons deux idées qui améliorent les performances de la marche stochastique. La première est basée sur une relaxation de l'exactitude du prédicat d'orientation, tandis que la deuxième est basée sur lune tentative de divination de la longueur de cette marche.
Fichier principal
Vignette du fichier
RR.pdf (734.51 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

inria-00493046 , version 1 (17-06-2010)

Identifiers

  • HAL Id : inria-00493046 , version 1

Cite

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

Share

Gmail Facebook Twitter LinkedIn More