Published in

Elsevier, Theoretical Computer Science, 1(283), p. 203-221, 2002

DOI: 10.1016/s0304-3975(01)00076-7

Springer Verlag, Lecture Notes in Computer Science, p. 375-387

DOI: 10.1007/3-540-49126-0_29

Links

Tools

Export citation

Search in Google Scholar

Rounding Voronoi Diagram

Journal article published in 1999 by Olivier Devillers ORCID, Pierre-Marie Gandoin
This paper is made freely available by the publisher.
This paper is made freely available by the publisher.

Full text: Download

Green circle
Preprint: archiving allowed
Orange circle
Postprint: archiving restricted
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

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.