Voronoi Diagrams

Let S be a set of points in the plane called sites. For any point p in the plane let close(p) be the set of sites that realize the closest distance between p and the sites of S. For most points p, close(p) consists of only a single site. For some, close(p) contains two or more sites. The points p where close(p) contains two or more sites form the Voronoi diagram of S.

There is also a furthest site Voronoi diagram. For any point p of the plane let furthest(p) be the set of sites that realize the furthest distance between p and the sites of S. The points p where furthest(p) contains two or more sites form the furthest site Voronoi diagram S.

On the right you see a Voronoi diagram of a set of 50 points in the plane. The picture is a screenshot from the example of computing and verifying a Voronoi diagram.

Properties of Voronoi Diagrams

• A Voronoi diagram has a graph-like structure:
  • The nodes are the points p with |close(p)|>=3.
  • The edges are the maximal connected sets of points p with |close(p)|=2.
  • The faces are the maximal connected sets of points p with |close(p)|=1..
• Let e be an edge of the Voronoi diagram such that s and t are the two sites of S with close(p)={s,t} for all points of e. Then e is a straight line segment contained in the perpendicular bisector of s and t.
• Consider a face f of the Voronoi diagram and let s be the site such that close(p)={s} for all points of f.
  • The distance of all points of f to s is smaller than to all other sites.
  • f contains s.
  • f is an open convex polygonal region.

Representation of Voronoi Diagrams

Voronoi diagrams are represented by parameterized plane map of type GRAPH<CIRCLE,POINT>.

• There is a node in the graph for every node of the Voronoi diagram.
• We place a "node at infinity" on every unbounded edge of the Voronoi diagram.
• There is an edge in the graph for every edge of the Voronoi diagram.

• Every edge is labeled with the site whose region lies to the left. See also Orientation and Sidedness.
• Every proper node v is labeled by a CIRCLE(a,b,c) where a,b,c are distinct sites whose regions are incident to v. The center of the circle is the position of v in the plane.
• Every node v at infinity lies on the perpendicular bisector of two sites a and b. v is labeled by CIRCLE(a,x,b) where x is an arbitrary point collinear with a and b and v lies to the left of the oriented segment from a to b.

Remark: We use the notation CIRCLE (POINT) to indicate that the algorithm works both for circles (points) and rat_circles (rat_points). See also Writing Kernel Independent Code.

Running Time

Verification of Voronoi Diagrams

	bool Is_Voronoi_Diagram(const GRAPH<CIRCLE,POINT>& G, 
	                        delaunay_voronoi_kind kind)

See also:

Data Types for 2-D Geometry

Parameterized Graphs

Orientation and Sidedness

Writing Kernel Independent Code

Verification of Geometric Structures

Duality between Voronoi and Delaunay Diagrams

Delaunay Diagrams

Applications:

Extremal Circles

Minimum Width and Minimum Area Annuli

Curve Reconstruction

Geometry Algorithms

Geometry

Graphs

GeoWin

Manual Entries

Manual Page of Geometry Algorithms