I should stress that I want to add a disk that's as close as possible to the first disk (measuring center-to-center), NOT the disk that's as close as possible to the corner (measuring from the center of the disk to the corner point of the quadrant). The two disks are usually the same, but not always. I have reasons for this preference, which are a bit arcane so I won't post them here; but if anyone is thinking of working on this problem and wants to know why I have this preference, I can try to cobble together a coherent explanation. Jim Propp On Mon, Jan 27, 2014 at 1:17 AM, James Propp <jamespropp@gmail.com<javascript:_e({}, 'cvml', 'jamespropp@gmail.com');>
wrote:
Given a quadrant, and a unit disk tightly wedged in its corner, and some other unit disks touching that one, let's play a game where we add more unit disks, always adding a new disk that's as close as possible to the original disk (the one that's tightly wedged in the corner).
For instance, suppose
(A) we add a second unit disk that's tangent to the first disk and to one of the rays bounding the quadrant, and a third disk that's tangent to the first two disks (so that the centers of the three disks form an equilateral triangle one of whose sides is parallel to the ray). See the attachment for pictures of this case and the other three cases described below.
If we now continue adding disks greedily, I claim (but have not proved) that you get a subset of the standard close-packing of the plane by unit disks. (Proof, anyone?)
Things are more interesting in some other cases, though, such as
(B) The second disk is tangent to the first disk and to one of the rays bounding the quadrant, and the third disk is tangent to the first disk and to the other ray bounding the quadrant (so that the centers of the three disks form an isosceles right triangle).
(C) The centers of the three disks form an equilateral triangle (as in (A)), but one that is symmetrical with respect to the line that bisects the quadrant.
(D) We start with just two disks, and the second disk (tangent to the first) has its center lying on the line that bisects the quadrant.
In the event of a tie between two locations where one might add the next disk, I'd like to follow Yogi Berra's Imperative ("When you see a fork in the road, take it") and follow both branches of the tree. Actually, "tree" is the wrong word, since hopefully there'll be some convergence going on as well.
Note that if we start with just one initial disk, then there are infinitely many ways to add the second disk at distance 0 from the initial disk (or distance 2, if you measure from center to center). So I won't ask the question in this case, at least not yet; following the Yogi Berra Imperative would give us too many possibilities to consider.
My belief is that in cases (B)-(D), something approximating the standard dense-packing of the plane by unit disks will emerge, but with interesting defects, and that in each case the picture as the number of disks goes to infinity will be unique (up to a flip).
It should be possible to explore this computationally, but my programming chops aren't up to the task. One would need to find a good way to represent the arrangement of the disks, and then find a way to solve the problem of where to place the next disk, using exact arithmetic so that ties can be detected. But I'm guessing that some of you (Bill Gosper and Veit Elser in particular) have already dealt with problems like this one, and may even have some off-the-shelf code that would be useful.
Note: This is a reboot of my thread "Greedily packing disks in a sector" from a year ago. I asked that question in the context of a 72 degree sector, but I now realize that the 90 degree sector is worth looking at too, and might yield some pretty pictures and pretty mathematics.
Jim Propp