# What is this data structure/concept where a plot of points defines a partition to a space

I encountered an algorithm to solve a real world problem, and I remember a class I took where I made something very similar for some for a homework problem.

Basically it's a plot of points, and the lines are drawn to be equidistant between two points. It forms a perfect partition where the lines around the point form the shape of area that is closest to that point. Does this ring a bell to anyone? I've had a tough time googling descriptions and getting results. And I don't know how else to describe it. Hopefully the picture helps.

• Viewed 1667 times since yesterday? Is SE being hacked? Jan 23 '19 at 18:35
• @HEKTO it was displayed as one of the "Hot Network Questions". Jan 25 '19 at 0:53

In the simplest case, shown in the first picture, we are given a finite set of points $${p_1, \cdots, p_n}$$ in the Euclidean plane. In this case each site $$p_k$$ is simply a point, and its corresponding Voronoi cell $$R_k$$ consists of every point in the Euclidean plane whose distance to $$p_k$$ is less than or equal to its distance to any other points. Each such cell is obtained from the intersection of half-spaces, and hence it is a convex polygon. The line segments of the Voronoi diagram are all the points in the plane that are equidistant to the two nearest sites. The Voronoi vertices (nodes) are the points equidistant to three (or more) sites.