Rounding Voronoi Diagram

Olivier Devillers 1 Pierre-Marie Gandoin 1
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Computational geometry classically assumes real-number arithmetic which does not exist in actual computers. A solution consists in using integer coordinates for data and exact arithmetic for computations. This approach implies that if the results of an algorithm are the input of another, these results must be rounded to match this hypothesis of integer coordinates. In this paper, we treat the case of two-dimensional Voronoi diagrams and are interested in rounding the Voronoi vertices to grid points while interesting properties of the Voronoi diagram are preserved. These properties are the planarity of the embedding and the convexity of the cells. We give a condition on the grid size to ensure that rounding to the nearest grid point preserves the properties. We also present heuristics to round vertices (not to the nearest grid point) and preserve these properties.
Type de document :
Communication dans un congrès
Discrete Geometry and Computational Imagery, 1999, Noisy le grand, France. springer, 1568, pp.375-387, LNCS. 〈http://www.dgci-conference.org/〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01179442
Contributeur : Olivier Devillers <>
Soumis le : mercredi 22 juillet 2015 - 14:50:12
Dernière modification le : samedi 27 janvier 2018 - 01:30:45

Identifiants

  • HAL Id : hal-01179442, version 1

Collections

Citation

Olivier Devillers, Pierre-Marie Gandoin. Rounding Voronoi Diagram. Discrete Geometry and Computational Imagery, 1999, Noisy le grand, France. springer, 1568, pp.375-387, LNCS. 〈http://www.dgci-conference.org/〉. 〈hal-01179442〉

Partager

Métriques

Consultations de la notice

149