Voronoiverkko

Voronoiverkko, also known as a Voronoi diagram or Voronoi tessellation, is a partitioning of a plane into regions based on distance to a specified set of points, known as seeds, sites, or generators. Each region consists of all points closer to its corresponding seed than to any other seed. The boundaries between regions are perpendicular bisectors of the line segments connecting the seeds.

The concept was named after the Russian mathematician Georgy Voronoy, who first described it in 1908. However, the idea had been previously explored by other mathematicians, including René Descartes in the 17th century. Voronoi diagrams have applications in various fields, including geography, crystallography, and computer science.

In geography, Voronoi diagrams are used to analyze spatial patterns and to determine the influence areas of geographical features. In crystallography, they are used to model the structure of crystals. In computer science, they are used in algorithms for nearest neighbor search, data compression, and image processing.

The dual of a Voronoi diagram is a Delaunay triangulation, which is a triangulation of the same set of points such that no point is inside the circumcircle of any triangle. The two structures are closely related and can be transformed into each other.