**Voronoi
templates** in the **Transform
dialog** and Voronoi functions in SQL create Voronoi diagrams
for a set of points.

Suppose we have a drawing of points. A Voronoi diagram divides the drawing into regions around each point that are shaped so that the borders of the regions are equidistant from the two nearest points.

The illustration seen above shows the effect of the **Voronoi
Diagram, Lines** template with the original points shown with reduced
transparency.

By drawing lines to mark out Voronoi cells, or by creating areas in
the shape of those cells, we divide up, that is * tile*
or

The **Transform
dialog** provides three **templates
for drawings** to create Voronoi diagrams:

**Voronoi Diagram**- Create area objects for each Voronoi cell.

**Voronoi Diagram, Lines**- Create line objects at the border of each Voronoi cell.

**Voronoi Diagram, Points**- Create point objects at the intersections of the borders of the Voronoi cells. Rarely used.

The illustration seen above shows the effect of the **Voronoi
Diagram, Lines** template with the original points shown with reduced
transparency.

Geom |
The |

Inflate X, Y |
Factors by which to increase the bounding box used for clipping infinite regions. See discussion below. |

Tolerance |
Value within which
objects are judged adjacent, for computations required to draw
borders between Voronoi regions. Use |

Options |
See the |

Based on the drawing of points, create a drawing of areas that form a Voronoi diagram for those points.

The **Voronoi Diagram** template
preview, as seen above, creates area objects for the Voronoi diagram.

Based on the drawing of points, create a drawing of lines that form a Voronoi diagram for those points.

The **Voronoi Diagram** template
preview, as seen above, creates line objects for the Voronoi diagram.
The relationship of the lines to the original can be
seen by adding the original points to the illustration below:

Based on the drawing of points, create a drawing of points at the intersection of borders of lines or areas that would form a Voronoi diagram for those points.

The **Voronoi Diagram** template
preview, as seen above, creates line objects for the Voronoi diagram.
To see the relationship of the Voronoi points to the
Voronoi regions, we can overlay with slight transparency a drawing of
Voronoi lines:

Manifold will automatically clip regions that grow to infinite extent in a Voronoi diagram. The horizontal boundaries at the top of Voronoi diagrams in illustrations above show clipping where the upper regions would diverge and thus grow to infinite extent.

Zooming out in the **Voronoi Diagram,
Lines** template preview we can see how a clipping box is constructed
using locations where the borders of regions converge. Such
clipping is a convenience as Voronoi diagrams are almost always manually
clipped to some reasonable area of interest when used in real life applications.

**Important:** Clipping as shown
in **previews** is approximate. Zooming
in or out will change the apparent extents of the clipping

Suppose we have a few hundred environmental sampling stations scattered throughout a region. We also have a dozen data collection centers, numbered 1 through 12, within the region. Environmental sampling stations are connected to a data collection center using radio communications so we would like to assign each sampling station to the nearest data collection center.

To do this we first use a drawing of the data collection centers to create a Voronoi Area surrounding each center.

We can then use an **Overlay**
template to transfer the identification number of each data collection
center to the Voronoi cell that encloses it. Next, we can use an **Overlay**
once more to transfer the identification number from each Voronoi cell
to all of the sampling station points within each cell.

The result is that each sampling site will have a field that contains the data collection center number that services it, and in all cases the data collection center will be the closest collection center to that sampling site.

Voronoi diagrams are also known in some cultures as Dirichlet or Thiessen
tessellations. Although individual investigators have used this powerful
concept informally at least as far back as **Descartes** in 1644 the
key researchers formally developing this concept were Dirichlet and Voronoi.

J. P. G. Lejeune Dirichlet (1805 - 1859)

Dirichlet used a special form of the Voronoi tessellation in his study of positive quadratic forms. Dirichlet was born in a part of the French Empire long disputed back and forth between France and Germany, studied in Paris and settled down to an overworked and productive career in Germany. Voronoi later published a generalization of Dirichlet's concept that would apply to higher dimensions and so introduced the concept in its modern form.

Georgi. F. Voronoi (1868 - 1908)

Voronoi was born in Russia on 28 April 1868 and graduated from the University of St. Petersburg in 1889, winning the Bunyakovsky prize for his Master's thesis and again a second time for his Doctor's thesis. He was a lecturer at Warsaw University and contributed to the theory of algebraic numbers and the geometry of numbers.

At times Voronoi wrongly is claimed to be a German mathematician, an error repeated in some web sites. Even more inaccurately, some people refer to Voronoi's work by crediting the concept to Alfred Thiessen, an American meteorologist.

Thiessen used the idea of Voronoi diagrams much later than either Dirichlet or Voronoi, beginning only in 1911 to apply them to the study of meteorology. It is always possible Thiessen felt he had independently derived the concept (as have many workers in the years since Voronoi's publications). As a meteorologist Thiessen might not have known of the mathematical work of professional mathematicians such as Dirichlet or Voronoi.

But is unfortunate that some writers who certainly knew of Voronoi's work and Dirichlet's work would deny either Voronoi or Dirichlet credit while advancing Thiessen as the inventor of a concept that Voronoi and Dirichlet developed far earlier and in much more complete form.

Whatever the reason for the wrong attribution, in modern times if we are not to inadvertently repeat the error we should use the term "Voronoi" or "Dirichlet" tessellations for this concept. The term “Voronoi” is used by Manifold because it was Voronoi who presented the mathematics in the contemporary form used within Manifold. To honor Dirichlet It is tempting to suggest using “Voronoi-Dirichlet" diagrams. Has a nice ring to it.

"Voronoi" is pronounced by English speakers as "Vo - ro - noi" with a short "o" sound, like the "o" in "or", for the first two syllables. The third syllable is pronounced like the "noi" in "noise". The stress is on the third syllable. Russian speakers will pronounce the name with such a short "o" in the first two syllables that it sounds like "uh" or even "ah".

"Dirichlet" is pronounced exactly as it is spelled, that is, if you are French: "Dee - reesh - lay" with the stress mostly on the first syllable. Although he lived and worked in Germany Dirichlet retained the French pronunciation of his name.

Transform Templates - Drawings