Theorem
A rectangle of width d and height 2d can contain at most
six points such that any two points are at distance at least d
Proof
This will be an intuitive proof by construction. We shall begin to place
points into the box until it is impossible to add any more. First imagine
a circle of radius d around each point representing the area that
we are not allowed to insert another point into. We can minimize the
overlapping area of such a circle with the rectangle by placing the point
on the corner of the rectangle as in the following figure:
Hence we can place points somewhere inside the light blue area or on the
edges of the circles. Hence we put one more in the middle of the left side
leaving the entire box covered except for the remaining two corners and the
middle of the right side (all three of these points being right on the
boundaries of the circles). Once we do this we have the following
structure:
Note that there are now six points in the square. If you try to move any
one of these points in any direction within the boundaries of the rectangle,
then you would be moving two points too close toghether.
Hence we can't possibly add any more points to this rectangle without
putting violating the distance property between the points. Therefore
six is the maximum number of points we can have.
QED.
Sam Bakhtiar SANJABI
Last modified: Wed Apr 12 01:00:00 EDT 2000