Discrete Voronoi-like Partition of a Mesh on a Cellular Automaton in Asynchronous Calculus

Nassim Kaldé (1) , Olivier Simonin (2)

1 MAIA - Autonomous intelligent machine
2 DYNAMID - Dynamic Software and Distributed Systems

This report presents an approach for asynchronously computing a Voronoi skeleton in a decentralized fashion on a regular grid of cells with a von Neumann neighborhood. To our knowledge, no previous work asynchronously solves this problem in a decentralized fashion. The methods given in this paper describe algorithms for extracting an area voronoi diagram skeleton and a pseudo line-like voronoi diagram skeleton. Algorithms are implemented in simulation and executed on maps in which we consider different kind of sources defined as polygonal shapes. Such work can be useful for robotic navigation.

Ce rapport présente une approche pour le calcul asynchrone et décentralisé d'un squelette de Voronoi sur une grille régulière de cellules possédant un voisinage de von Neumann. À notre connaissance, aucun travail précédent ne résout ce problème de manière asynchrone et décentralisée. Les méthodes données dans ce papier décrivent des algorithmes d'extraction du squelette d'un diagramme de voronoi d'aire ou de ligne. Ces algorithmes ont été implémentés en simulation et éxécutés sur des cartes dans lesquelles nous avons considéré différentes sources de forme polygonale. Ce travail peut être utile en navigation robotique.

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Nassim Kaldé, Olivier Simonin. Discrete Voronoi-like Partition of a Mesh on a Cellular Automaton in Asynchronous Calculus. [Research Report] RR-8547, INRIA. 2014. ⟨hal-01006458⟩