Your attachments won't get past the door. Put 'em up on Dropbox or Google Drive and post the URL if you want people to see 'em! WFL On 1/28/14, James Propp <jamespropp@gmail.com> wrote:
Since nobody seemed likely to step in with some good clean code for my problem, I thought it was time to enlist help from dark and mysterious forces of undoubted power that cannot be entirely trusted, namely, the optimization routines built into Mathematica.
I had to give up on following the Yogi Berra Principle, since Mathematica apparently doesn't report multiple optima when there's a degeneracy. (But dark and mysterious forces always exact a price for their services, don't they?)
The attached PDF gives plots of the centers of the disks. Assuming Mathematica isn't leading me astray, the disks in case A do indeed form the standard close-packing, at least for a while. In case B we get something more interesting (though it's not clear to me whether the configuration shown is unique up to a flip or whether there are a whole lot of similar configurations that you get when you follow all branches). In cases C and D, the computations are quite time-consuming, so I wasn't able to go far enough to get much of a sense of what might be going on. D might give a close-packing, or it might not.
Does anyone know of a computer algebra system that might be better at this sort of thing (either more reliable or faster --- preferably both!)?
Jim Propp
On Mon, Jan 27, 2014 at 9:56 PM, James Propp <jamespropp@gmail.com> wrote:
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> 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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun