Rounding of geometric structures

Computational geometry usually relies on the use of exact numbers which are not representable in an actual computer. A solution consists in using integer coordinates and exact computations. Such an approach implies that the results of an algorithm must be rounded if it is needed to reinject them in another algorithm.

Voronoi diagrams

In the case of Voronoi diagrams in two dimensions, we need to round the Voronoi vertices on a regular grid while keeping interesting properties of Voronoi diagrams such as planarity or convexity of the cells.

If the vertices are rounded to the nearest grid points, such properties may be lost. It happens in fact in the example on the left, where the Voronoi diagram (in blue) is rounded (in red) making a cell (the yellow one) non convex.

Figure on the right shows an example where it is impossible to round the Voronoi (blue) diagram on the (orange) grid with good properties.

Sufficient condition

When the diagram is rounded, a vertex is moved in the worst case by the half diagonal of a pixel. Given an angle ABC we may consider the worst case for the rounded angle A'B'C' and get a sufficient condition to obtain a correct rounding of the diagram.

More on this topic

Last modified: Mon Nov 29 13:50:40 MET 1999 Olivier Devillers P.-M. Gandoin Topics PRISME Homepage la même page en français