Drawing Blanks

Premature Optimization is a Prerequisite for Success

Closest neighbors

leave a comment »

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?


Written by bbzippo

07/02/2012 at 3:27 am

Posted in math

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: