# Voronoi diagram

Jump to: navigation, search

A very important geometric structure in computational geometry, named after G.F. Voronoi. The earliest significant use of Voronoi diagrams seems to have occurred in the work of C.F. Gauss, P.G.L. Dirichlet and Voronoi on the reducibility of positive-definite quadratic forms (cf. Quadratic form).

Let $S = \{ p _ {1} \dots p _ {n} \}$ be a set of $n$ points in $\mathbf R ^ {d}$. The Voronoi diagram generated by $S$ is the partition of the $\mathbf R ^ {d}$ into $n$ convex cells, the Voronoi cells, $V _ {i}$, where each $V _ {i}$ contains all points of $\mathbf R ^ {d}$ closer to $p _ {i}$ than to any other point:

$$V _ {i} = \left \{ x : {\forall j \neq i, d ( x,p _ {i} ) \leq d ( x,p _ {j} ) } \right \} ,$$

where $d ( x,y )$ is the Euclidean distance between $x$ and $y$.

See also Delaunay triangulation.

How to Cite This Entry:
Voronoi diagram. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Voronoi_diagram&oldid=49164
This article was adapted from an original article by O.R. Musin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article