Walking Faster in a Triangulation
Résumé
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.
Domaines
Géométrie algorithmique [cs.CG]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...