Asynchronous Computing of a Discrete Voronoi Diagram on a Cellular Automaton Using 1-Norm: Application to Roadmap Extraction

Nassim Kaldé 1 Olivier Simonin 2 François Charpillet 1
1 MAIA - Autonomous intelligent machine
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
2 DYNAMID - Dynamic Software and Distributed Systems
CITI - CITI Centre of Innovation in Telecommunications and Integration of services
Abstract : This article addresses the problem of computing a Voronoi diagram in a distributed fashion without any synchronization heuristic. To our knowledge, no previous work asynchronously solves this problem. We investigate a simple case of asynchronism and tackle this challenge in a decentralized fashion on a grid of communicating cells with a von Neumann neighborhood. We describe algorithms for extracting single site, area and pseudo line Voronoi diagrams. These algorithms are implemented and executed on maps in which we consider different kinds of sites defined as simple polygonal shapes to extract roadmaps.
Type de document :
Communication dans un congrès
IEEE International Conference on Tools with Artificial Intelligence (ICTAI), Nov 2014, Limassol, Cyprus
Liste complète des métadonnées

https://hal.inria.fr/hal-01076951
Contributeur : Nassim Kaldé <>
Soumis le : jeudi 23 octobre 2014 - 15:28:50
Dernière modification le : samedi 27 octobre 2018 - 01:19:47

Identifiants

  • HAL Id : hal-01076951, version 1

Citation

Nassim Kaldé, Olivier Simonin, François Charpillet. Asynchronous Computing of a Discrete Voronoi Diagram on a Cellular Automaton Using 1-Norm: Application to Roadmap Extraction. IEEE International Conference on Tools with Artificial Intelligence (ICTAI), Nov 2014, Limassol, Cyprus. 〈hal-01076951〉

Partager

Métriques

Consultations de la notice

223