[math-fun] Continuous Urinal Protocol
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
A and B are points on an ellipsoid E. S is the shortest path on the ellipsoid's surface between A and B . Does S always lie in a plane? Steve Gray
I don't actually know the answer to this, but it immediately calls to mind a favourite mathematical model from long ago, of a (filled) ellipsoid constructed from two families of interlocking circular discs. WFL On 6/26/11, Stephen B. Gray <stevebg@roadrunner.com> wrote:
A and B are points on an ellipsoid E. S is the shortest path on the ellipsoid's surface between A and B .
Does S always lie in a plane?
Steve Gray
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
No, the shortest path does not always lie on a plane. I'm pretty sure that the geodesic flow on an ellipsoid has been studied quite extensively. I've seen pictures of geodesics, which show no particular patterns. Typically there 3 simple closed geodesics (through the major axes) and no more; that is inconsistent with all geodesics lying in a plane. But those things are based on partially remembered "authority" which I don't want to look up right now. Here's a more direct way one can see, for the special case of ellipsoids that are surfaces of revolution: Geodesics on a surface of revolution satisfy the principle of conservation of angular momentum about the axis of revolution, when traversed at unit speed. For any given value of angular momentum, there is a band on the ellipsoid (might be empty, is the whole ellipsoid <==> ngular momentum is 0) where there are unit tangent vectors with the given angular momentum. In the interior of the band, there are two solutions; at the two circles that form the boundary of the band, there is only one soution at each point, but these circles are not geodesics; the geodesics go to the boundary on one "sheet" of solutions, then go out on the other "sheet". Each geodesic oscillates, back and forth, from one boundary curve to the other, with a certain period; the period depends on the value of angular momentum. Usually it has an irrational relation the period of a meridian circle, and such geodesics are dense in the band. This is roughly the pattern of how thread or kite string winds up on a round spool as it gets a slight bulge in the middle. Bill Thurston On Jun 26, 2011, at 1:16 PM, Stephen B. Gray wrote:
A and B are points on an ellipsoid E. S is the shortest path on the ellipsoid's surface between A and B .
Does S always lie in a plane?
Steve Gray
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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
participants (5)
-
Adam P. Goucher -
Bill Thurston -
Fred lunnon -
Henry Baker -
Stephen B. Gray