# 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, 2019 at 18:35
• @HEKTO it was displayed as one of the "Hot Network Questions". Jan 25, 2019 at 0:53

## 2 Answers

What you described is Voronoi diagram.

Here is an excerpt from Wikipedia.

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.

• +1. I refrained from mentioning them and went for implementations because I remember my professors mentioning them with a footnote that Voronoi Diagrams are computationally quite complex to implement in higher dimensions. So simple kNN implementations get the job done much better. However the condition that "lines are drawn to be equidistant between two points" may not be fulfilled. Jan 22, 2019 at 6:48

You are looking for a Multi-Class Classification Algorithm. I suggest you have a look at: