Voronoi Diagrams

Given a discrete set of points $S\subset\mathbb{R}^2,$ an important task is to describe or construct, for each $p\in S,$ the set of points $x\in\mathbb{R}$ that are nearer to $p$ than to any other point $q\in S.$ Such sets always exist and are variously known as Voronoi, Dirichlet, or Tiessen or cells, or polygons. Their union forms Dirichlet's tessellation, whereas the union of their borders is usually referred to as Voronoi diagram.

So, by definition, the Voronoi cell of $p\in S$ is

$\mbox{Vor}(p) = \{x\in\mathbb{R}^{2}:\space ||x-p||\lt ||x-q||,\space\mbox{for all}\space q\in S, q\ne p\},$

$||s||$ is the Euclidean length of $s\in\mathbb{R}^2:$ $||(x,y)||=\sqrt{x^{2}+y^{2}}.$

Voronoi cells of a two-point set $S$ are half-planes separated by the perpendicular bisector of the segment between the points. It follows that, in general case, $\mbox{Vor}(p)$ is the intersection of half-planes formed by the perpendicular bisectors of the segments joining $p$ to other points in $S.$ As the intersection of convex sets, $\mbox{Vor}(p)$ is always convex. It is always a polygon, if infinite rays or lines are accepted as legitimate sides of a region.

In the context of Voronoi diagrams, the points of $S$ are usually called sites. The graph with the sites as vertices, and edges that join the sites with common border, is known as the dual graph, the graph dual to the graph formed by the edges of Voronoi diagram.

The applet below helps visualize Voronoi diagrams and their dual graphs.

Fill

Smooth

Sites

Graph

Arcs

Clear

To create a site press the mouse button. You may start dragging immediately or release the button and look for another location. (You have to start with two clicks at different locations. Sometimes, due to a bug, a site is getting lost. I apologize for the inconvenience.) The applet has six button controls that appear in the upper right corner when the mouse moves into the applet area. The first four are toggles: Fill (fill or not Voronoi cells), Smooth (smooth the borders of Voronoi cells), Sites (show sites or not), Graph (show graph or not). The fifth button Arcs controls how edges of the dual graph are formed. There are four possibilities to cycle through: straight lines joining the sites; straight or broken lines, straight lines or splines, straight lines or circular arcs. (The extras come when a straight line joining two sites crosses the borders other than the common part of the two cells.) The last control is Clear.

Note that whenever the edges of the dual graph are straight or broken lines, the graph is planar. This is not always the case when the curved edges are permitted.

Acknowledgment

The applet above is a modification of the example found at the paper.org site. paper.js is a powerful JavaScript library developed by Jürg Lehni and Jonathan Puckey.

References

S. L. Devadoss, J. O'Rourke, Discrete and Computational Geometry, Princeton University Press (May 1, 2011)

71548427