Celestial Walk: A Terminating, Memoryless Walk for Convex Subdivisions

Wouter Kuijper (1) , Victor Ermolaev (1) , Olivier Devillers (2)

1 Nedap Security Management [Groenlo]
2 GAMBLE - Geometric Algorithms and Models Beyond the Linear and Euclidean realm

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.

Domaines: Géométrie algorithmique [cs.CG]; Synthèse d'image et réalité virtuelle [cs.GR]

Wouter Kuijper, Victor Ermolaev, Olivier Devillers. Celestial Walk: A Terminating, Memoryless Walk for Convex Subdivisions. Journal of Computer Graphics Techniques, 2018, 7 (3), pp.29-49. ⟨hal-01867771⟩