Separating Points in a Rectangle
Benjamin L. Schwartz · Mathematics Magazine · 1973
1. Problem statement. In the Journal of Recreational Mathematics of July 1969, problem 88 [9] asks what is the minimum distance between any pair of points in a set of N points which are placed in the closed unit square to maximize this minimum distance. The arrangement (or arrangements) of the N points that achieves this separation is also desired. Solutions are known for N = 2, 3, 4, 5, 6, 8, and 9 [6, 7, 8,]. (For N = 7, Ref. [7] contains an arrangement and an assertion that the author has privately proved it to be optimal. However no published proof is known to this writer.) For larger values of N, M. Goldberg [2] has empirically obtained lower bounds by finding good arrangements for all N up to 30, and for selected higher values of N up to 340, J. Schaer [5] improved Goldberg's result for N = 10. J. S. Byrnes [1] has noted that substantial and unexpected theoretical difficulties arise in considering this problem, making the investigations quite complicated even for moderate values of N. (The author's proof for N = 6 requires 10 printed pages [8].) There are many obvious generalizations to this problem. One could consider separating points in a 3-dimensional or n-dimensional cube, in an arbitrary plane polygon, in a circle [3, 4], or indeed in any arbitrary region. The present paper considers a very simple extension to the original problem, and even this rapidly leads to some subtle features. Our problem will be to place N points in an arbitrary rectangle to maximize the minimum separation between any two. We shall solve the cases N = 2, 3, 4, and 5. Our methods are entirely self-contained; there will be no appeal to the known solutions for the square, although of course the ideas used in the prior solutions have been suggestive to us. The solutions for the square will emerge as special cases from the present investigation, providing a partial check. We shall normalize the problem by taking as the unit of measure the longer side of the constraining rectangle. Hence the problem can be stated as maximizing the separation of N points in a rectangle, 1 by A units, where 0 < A < 1.