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.
Liste complète des métadonnées

Cited literature [3 references]  Display  Hide  Download


https://hal.inria.fr/hal-01867771
Contributor : Olivier Devillers <>
Submitted on : Tuesday, September 4, 2018 - 3:50:20 PM
Last modification on : Tuesday, December 18, 2018 - 4:18:26 PM
Document(s) archivé(s) le : Wednesday, December 5, 2018 - 5:51:08 PM

Files

Kuijper2018Walk(1).pdf
Files produced by the author(s)

Identifiers

  • 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〉

Share

Metrics

Record views

467

Files downloads

52