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.

### 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.

Data Types for 2-D Geometry

Parameterized Graphs

Duality between Voronoi and Delaunay Diagrams

Delaunay Diagrams

### Applications:

Extremal Circles

Minimum Width and Minimum Area Annuli

Curve Reconstruction

Geometry Algorithms

Geometry

GeoWin

### Manual Entries

Manual Page of Geometry Algorithms