Celestial Walk: A Terminating Oblivious Walk for Convex Subdivisions - Archive ouverte HAL Access content directly
Reports (Research Report) Year : 2017

Celestial Walk: A Terminating Oblivious Walk for Convex Subdivisions

La marche céleste: une marche oublieuse dans les subdivisions convexes à terminaison garantie

(1) , (1) , (2)
1
2

Abstract

We present a new oblivious walking strategy for convex subdivisions. Our walk is faster than the straight walk and more generally applicable than the visiblity walk. To prove termination of our walk we use a novel monotonically decreasing distance measure.
Nous présentons une nouvelle stratégie de marche pour les subdivisions convexes. Cette stratégie est oublieuse, c’est à dire que la prochaine cellule visitée ne dépends pas des cellules visitées précédemment. Notre marche est plus rapide que la marche rectiligne et s’applique à des subdivisions plus générales que la marche par visibilité. La démonstration de terminaison repose sur la décroissance monotone d’une nouvelle distance mesurant le progrès de la marche
Fichier principal
Vignette du fichier
RR-9099.pdf (793.34 Ko) Télécharger le fichier
Vignette du fichier
vignette-cw.png (9.77 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Format : Figure, Image
Loading...

Dates and versions

hal-01610205 , version 1 (12-10-2017)

Identifiers

Cite

Wouter Kuijper, Victor Ermolaev, Olivier Devillers. Celestial Walk: A Terminating Oblivious Walk for Convex Subdivisions. [Research Report] RR-9099, INRIA Nancy. 2017. ⟨hal-01610205⟩
284 View
73 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More