Theoretical Input - Voronoi diagrams
A Voronoi diagram is a way of dividing space into a number of regions.
Definition:
The Voronoi region of a point – called sites or generators – is the set of all points in the plane that are closer to than any other site. The set of all Voronoi regions is called Voronoi diagram.
Voronoi diagram for two points
Voronoi diagram for more points
Six Examples
You can construct the Voronoi diagrams with GeoGebra.
Answer the following questions!
- In Example I you find one point in the middle where three edges converge. What can you say about the distances of that point to the centers?
- Does Example II also have such a point?
- In the Example III and IV only one center is not in the same place. However, the Voronoi diagrams differ considerably. Try to indicate the cause of that difference.
- In Example V the centers lie on one line and thus the diagram is fairly easy to draw. What can you say about the mutual position of the edges and the shape of the Voronoi cells?
- Example VI has lots of centers. But thanks to the regularity, sketching of the edge diagram is again a simple affair. Once one cell is known, the rest follows automatically. Do you know anything in nature which has this pattern as a partition?