Celestial Walk: A Terminating Oblivious Walk for Convex Subdivisions
La marche céleste: une marche oublieuse dans les subdivisions convexes à terminaison garantie
Résumé
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
RR-9099.pdf (793.34 Ko)
Télécharger le fichier
vignette-cw.png (9.77 Ko)
Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Figure, Image
Loading...