Voronoi Tessellation


Scalation of flippers and head of a sea turtle looking like Voronoi cells. Soap foam looking like Voronoi cells. Veins in a leaf looking like Voronoi cells.
Green sea turtle. source: Brocken Inaglory, Wikimedia Commons. Soap foam bubbles. source: André Karwath, Wikimedia Commons. Veins in a Poinsettia leaf. source: Fasaxc, Wikimedia Commons.

A simple Voronoi diagram can be described as: Given a finite set of points, called seeds, sites or generators, in a 2D plane. Each point lies in a corresponding region or cell. A seed's corresponding Voronoi cell consists of every point in the plane whose distance to this seed is less than or equal to its distance to any other seed in the plane. The line segments of the Voronoi diagram are all the points in the plane that are equidistant to the two nearest seeds. The Voronoi vertices (aka nodes) are the points equidistant to three or more seeds.

Voronoi diagrams are used to model phenomena and processes involving growth or spatial division, such as cell architecture in biological tissue, microstructure of polycrystalline metal, nearest neighbor searches, mesh generation, etc, etc.

Fig.2. forming a Voronoi diagram by radial growth from a number of randomly positioned seeds.

Static SVG image of a Voronoi diagram with random seeds. Stand-alone version of this Voronoi grower.

In figure 2 the seeds are randomly positioned in the plane. We can also position the seeds in a certain pattern. In figure 3 a number of seeds are positioned on a straight horizontal line and one seed is positioned above that.

Distance between focus and directrix:

Points on the directrix:

Fig.3. A Voronoi diagram approaching a parabolic arc.

Static SVG image of a "Voronoi parabola". Stand-alone version of this "Voronoi parabola" app.

The more the number of points on the horizontal line approaches infinity, the more the edge of the cell belonging to the one point above the horizontal line looks like a parabolic curve. And indeed, a geometrical description of a parabola involves a point, the focus, a line, the directrix, and the parabola, being the locus of points equidistant from both the directrix and the focus. An infinite number of points on a straight line is actually a straight line, and hence a parabola can be viewed as a Voronoi diagram of two seeds: a point and a straight line.

So, seeds of a Voronoi diagram are not limited to points. In a plane a seed can be any line, circle, curve, etc. Figure 4 shows some examples.

cells of two seeds in a rectangular seed cell of one seed in a circular seed cell of one seed in a square seed


Voronoi cells of two seeds within a rectangular seed.

Voronoi cell of one seed within a circular seed (a definition of an ellipse by focus and circular directrix).

Voronoi cell of one seed within a square seed.

Every symmetry of a set of seeds is also a symmetry of the corresponding Voronoi diagram. So, using a symmetric arrangement of points in a plane, or any set of seeds with some set of symmetries, results in a symmetric tiling of the plane.

Seeds in spirals Voronoi cells in spirals Symmetric set of seeds Voronoi cells generated from symmetric set of seeds

Fig.5. Voronoi tilings (with some color effect) generated from symmetric point seed arrangements.

(Made with my JavaScript applications for Voronoi diagrams.)

This article is just a brief and shallow walk through the topic of Voronoi diagrams from a certain perspective. Many further extensions to this basic scheme are possible, such as weighted seeds (multiply all distances in a cell by some factor), other distance functions (metrics) or diagrams in more than two dimensions.