16
$\begingroup$

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. it looks like this

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.

$\endgroup$
2
  • $\begingroup$ Viewed 1667 times since yesterday? Is SE being hacked? $\endgroup$
    – HEKTO
    Jan 23, 2019 at 18:35
  • $\begingroup$ @HEKTO it was displayed as one of the "Hot Network Questions". $\endgroup$
    – John L.
    Jan 25, 2019 at 0:53

2 Answers 2

33
$\begingroup$

What you described is Voronoi diagram.

Here is an excerpt from Wikipedia.

Picture of Voronoi diagram 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.

$\endgroup$
1
  • 4
    $\begingroup$ +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. $\endgroup$
    – Sagnik
    Jan 22, 2019 at 6:48
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.