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.
