# Voronoi Diagrams (Reference request)

I'm studying some solid state physics and I saw the definition of Wigner-Seitz cell (or Voronoi). I'd like to see some examples of this with rigorous mathematics. I mean just some simple cases like honeycomb lattices and such.

Thanks

## 1 Answer

The web has a lot of good references on Voronoi diagrams especially for 2 dimensions, but basically the main thing you need to know is that the inequality that defines a point $x$ being closer to a point $x_1$ than another point $x_2$ forms a half-space (a hyper-plane and everything on one side of the hyper-plane) if you are using Euclidean distance. This is because all the squared variables in the inequality cancel, leaving a linear inequality. In 2-d the boundary hyperplanes are dividing lines. If you take the set of all such half-spaces for all pairs of points in a finite set $X$, and overlay them, then the Voronoi cell for a point $x_1 \in X$ is the intersection of all half-spaces separating $x_1$ from all other points $x_2 \in X$. An intersection of half-spaces is called a polyhedron. Thus a Voronoi diagram for a set of points is a polyhedral complex, which you can also read about. Another interesting fact you may want to read about online is that the so-called dual of a Voronoi diagram is what's called a Delaunay triangulation, which is basically a triangulation where the minimum angle amongst adjacent points in a cell is maximized. The duality is a pretty deep fact. If you want a book reference for all this, one good explanatory text is the Springer computational geometry book by Overmars et al.

• Thanks. I seems really interesting! – Abellan May 28 '15 at 0:10