## Closest neighbors

A simple but curious statement:

**In any finite set of points on the plane, there are points that have less than 4 closest neighbors.**

Not sure if this is a deep or useful observation.

Not sure if I have a rigorous proof. I’ll publish a sketch of a proof later.

And here is how you prove it:

Let s be the minimum pairwise distance in our set. Let S be the subset containing all points that have neighbors at the distance s.

Consider C=ConvexHull(S). There is at least one vertex in C with the angle less than 180 degrees. Easy to show that that vertex has at most 3 closest neighbors.

Ok, so there is no set in which each point has 4 (or more) closest neighbors.

Now build a set in which each point has exactly 3 closest neighbors. What is the minimal number of points in such set?

## Leave a Reply