What is a Voronoi Diagram?
Voronoi Diagram: A Voronoi diagram is a way of dividing a plane into regions based on proximity to a given set of points, so that every point in a region is closer to its associated site than to any other site.
Named after the Russian mathematician Georgy Voronoi, these diagrams are a key tool in computational geometry and spatial analysis. The core idea is simple: given a collection of points (called sites), the plane is partitioned so that each region contains all locations closest to one particular site.
Think of it like a map of influence zones , every location in the plane "belongs" to the nearest site.
Imagine five fire stations in a city. A Voronoi diagram divides the city into five zones, one per station. Every address in a zone is closer to that zone's fire station than to any other. In an emergency, you'd always send the station from the zone containing the incident.
Key Components of a Voronoi Diagram
A Voronoi diagram has four fundamental components:
-
Sites: The initial set of given points in the plane around which the diagram is constructed. Also called generators or seeds.
-
Cells: The region of the plane corresponding to each site , containing all points closer to that site than to any other.
-
Edges: The boundaries between adjacent cells. Every point on an edge is equidistant from exactly two sites (i.e., lies on the perpendicular bisector of the segment joining those two sites).
-
Vertices: Points where three or more edges meet. Every Voronoi vertex is equidistant from three or more sites.
Voronoi cells can be bounded (a finite polygon) or unbounded (extending to infinity). Sites on the "outside" of the diagram typically have unbounded cells. This is important when calculating areas , only finite regions can have a numerical area.
A useful memory aid: Sites → Cells → Edges → Vertices (S, C, E, V , think "Some Cells Edge Vertices"). Each component is derived from the previous one.