Tessellation

Voronoi Tessellation

The basic concept is a simple yet intuitively appealing one. Given a finite set of distinct points in a continuous Euclidean space, assign all locations in that space to the nearest member of the point set. The result is a partitioning of the space into a tessellation of convex polygons called the Voronoi diagram. The interior of each polygon contains all locations that are closest to the generator point, while the edges and vertices represent locations that are equidistant from two, and three or more generators, respectively. The tessellation is named for the Ukrainian mathematician Georgy Voronoï (1868–1908). However, given the simplicity of the concept, it has been “discovered” many times in many different contexts. Consequently, the tessellation is also known under a number of other names, the most prevalent in GIS being Dirichlet (after the German mathematician Peter Gustav Lejeune Dirichlet, 1805–1859) and Thiessen (after the American climatologist Alfred H. Thiessen, writing in the early 20th century). Note that the three regular planar tessellations (triangles, squares, and hexagons) can be created by defining the Voronoi diagrams of a set of points located on a hexagonal, square, and triangular lattice, respectively.

The basic Voronoi concept has been generalized in various ways, such as weighting the points, considering subsets of points rather than individual points, considering moving points, incorporating obstacles in the space, considering regions associated with lines and areas as well as points (and combinations of the three), examining different spaces (including noncontinuous ones and networks), and recursive constructions. Collectively, these tessellations are called generalized Voronoi diagrams (GVD). Their flexibility means that GVD have extensive applications in four general areas in GIS: defining spatial relationships, as models of spatial processes, point pattern analysis, and location analysis.

...