# Voronoi Tessellation

## Introduction

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.

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.

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.

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.

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.