Algorithmic Solutions > LEDA > LEDA Guide > Geometry Algorithms > Voronoi Diagrams

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.

Example of Vornoi Diagram

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.
Node and edge labels give information about the positions of the nodes of the graph in the plane and about the Voronoi regions:
  • 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

The running time of the algorithms for computing Voronoi diagrams is O(nlogn).

Verification of Voronoi Diagrams

The function
	bool Is_Voronoi_Diagram(const GRAPH<CIRCLE,POINT>& G, 
	                        delaunay_voronoi_kind kind)
checks whether G is a Voronoi Diagram of the points associated with its nodes. The flag kind allows to choose between the nearest (kind=NEAREST) and furthest (kind=FURTHEST) site version. See also Verification of Geometric Structures.

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




Please send any suggestions, comments or questions to leda@algorithmic-solutions.com
© Copyright 2001-2003, Algorithmic Solutions Software GmbH