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


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.
Sam Bakhtiar SANJABI
Last modified: Wed Apr 12 01:00:00 EDT 2000