HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download

Contributor : Olivier Devillers Connect in order to contact the contributor
Submitted on : Tuesday, September 4, 2018 - 3:50:20 PM
Last modification on : Friday, February 4, 2022 - 9:00:13 AM
Long-term archiving on: : Wednesday, December 5, 2018 - 5:51:08 PM


Files produced by the author(s)


  • HAL Id : hal-01867771, version 1



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. ⟨hal-01867771⟩



Record views


Files downloads