Celestial Walk: A Terminating, Memoryless Walk for Convex Subdivisions

Wouter Kuijper 1 Victor Ermolaev 1 Olivier Devillers 2
2 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
Abstract : A common solution for routing messages or performing point location in planar subdivisions consists in walking from one face to another using neighboring relationships. If the next face does not depend on the previously visited faces, the walk is called memoryless. We present a new memoryless strategy for convex subdivisions. The known alternatives are straight walk, which is a bit slower and not memoryless, and visibility walk, which is guaranteed to work properly only for Delaunay triangulations. We prove termination of our walk using a novel distance measure that, for our proposed walking strategy, is strictly monotonically decreasing.
Type de document :
Article dans une revue
Journal of Computer Graphics Techniques, Williams College, 2018, 7 (3), pp.29-49. 〈http://www.jcgt.org/published/0007/03/02/〉
Liste complète des métadonnées

Littérature citée [3 références]  Voir  Masquer  Télécharger


https://hal.inria.fr/hal-01867771
Contributeur : Olivier Devillers <>
Soumis le : mardi 4 septembre 2018 - 15:50:20
Dernière modification le : jeudi 20 septembre 2018 - 11:14:03

Fichiers

Kuijper2018Walk(1).pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01867771, version 1

Collections

Citation

Wouter Kuijper, Victor Ermolaev, Olivier Devillers. Celestial Walk: A Terminating, Memoryless Walk for Convex Subdivisions. Journal of Computer Graphics Techniques, Williams College, 2018, 7 (3), pp.29-49. 〈http://www.jcgt.org/published/0007/03/02/〉. 〈hal-01867771〉

Partager

Métriques

Consultations de la notice

426

Téléchargements de fichiers

33