I remember an analogous problem for squares & rectangles, which was studied by someone at Bell Labs a long, long time ago (50 years?). It may have been mentioned in Gardner's Scientific American column. They talked of placing people in an elevator so that the minimum distance was maximized. BTW, this problem doesn't work in Japan. If two Japanese strangers get on an empty subway car, they sit right next to one another, while if two American strangers get on an empty subway car, they sit at opposite ends. At 05:08 AM 6/26/2011, Adam P. Goucher wrote:
You may have encountered the (discrete) Urinal Protocol on the journal section of the xkcd website:
http://blog.xkcd.com/2009/09/02/urinal-protocol-vulnerability/
I propose the following alternative, the Continuous Urinal Protocol:
We have a unit disk, and a small real number d. A number of points are placed on the disk according to the following rules:
1. The first point is typically placed on the circumference of the disk.
2. Subsequent points are placed so as to maximise the minimum distance to any other point.
(To maintain the bathroom analogy, this could be a circular shower room.)
The circle fills up like so:
* Point 1 is placed on the circumference (Rule 1); * Point 2 is placed diametrically opposite; * Points 3 and 4 are placed to complete an inscribed square; * Point 5 is placed in the centre, forming a quincunx pattern; * Points 6, 7, 8 and 9 are placed at the vertices of a square, such that a regular octagon is described.
Beyond this point, some subset of the circumcentres of the eight triangles are filled up (3 or 4, depending on how the triangles are chosen).
So, the resulting pattern is (very slightly) non-deterministic, as choices between two equally optimal points can influence the entire configuration.
A stricter variant is to order the distances to each point in ascending order (to form an n-tuple), then choose the lexicographically greatest value. (i.e., if the closest points are tied, consider the next closest, ad infinitum.)
It is left as an exercise to the reader to demonstrate that this will necessarily result in patterns with order-4 rotational symmetry for all n = 4k + 1, k > 0. [Hint: Use Luke Betts' Theorem.]
Can we prove that this procedure is necessarily deterministic, up to symmetry?
Sincerely,
Adam P. Goucher