| Solution by the proposers.
Let r be the radius of the central disk. First look at a single
tangent configuration made up of the central disk, and two disks of
radii x and y. The three centres form a traingle with sides r+x, r+y,
and x+y; let theta=theta[r](x,y) be the angle at the centre of the disk
with radius r. Applying the law of cosines to this angle and
simplifying gives:
2xy
theta[r](x,y) = arccos(1 - -----------).
rr+ry+rx+xy
A routine calculation shows that the mixed partial derivative
theta[1,2] [The original has theta with "12" as a subscript; I believe
that means the partial derivatives of the function theta with respect
to its second argument and then its first, which would be y and then
x. -- edp] is given by:
rr
theta[1,2] = --------------------------;
2sqrt(xy) (rr+rx+ry)^(3/2)
therefore theta[1,2] > 0 (for x, y > 0). Integrating from a to a+s and
b to b+t (where s, t > 0) yields:
theta(a+s,b+t) + theta(a,b) > theta(a+s,b) + theta(a,b+t). (1)
Note that equality occurs if and only if s=0 or t=0.
We may assume n>=4 and a[1] >= a[2] >= ... >= a[n]; let D[i] denote the
disk with radius a[i]. And let S(r) denote
sum(theta[r](a[i],a[i+1]),i=1..n), the total angle made by the
configuration; when S < 2pi, then the disk of radius r is too large and
the ring is not yet closed up.
THEOREM. The largest inner radius r occurs by placing D[2] and D[3] on
either side of D[1], then D[4] alongside D[2], D[5] alongside D[3], and
so on around the ring.
Proof. By induction on n. We actually prove the stronger assertion
that for any radius r, S(r) for the configuration of the statement of
the theorem is not less than S(r) for any other configuration. This
sufficies, for if r is such that S(r) = 2pi, then S(r) for any other
configuration is not greater than 2pi.
For n=4 there are only three arrangements:
[Diagram showing three arrangements, each a circle with D[1], D[2],
D[3], and D[4] outside the circle at top, bottom, left, and right
of the circle. Counterclockwise from the top, the first circle
has D[1], D[3], D[2], and D[4]. Second circle is 1, 4, 3, 2.
Third circle is 1, 4, 2, 3.
The arrangements are labelled I, II, and III.]
for which (suppressing the subscripts r in the thetas)
S[I] = theta(a[1],a[2]) + theta(a[2],a[4]) + theta(a[3],a[4]) +
theta(a[1],a[3]),
S[II] = theta(a[1],a[2]) + theta(a[2],a[3]) + theta(a[3],a[4]) +
theta(a[1],a[4]),
S[III] = theta(a[1],a[3]) + theta(a[2],a[3]) + theta(a[2],a[4]) +
theta(a[1],a[4]).
By (1), S[I](r) >= S[II](r) >= S[III](r), which proves our assertion
for this case.
For the general case, suppose E[2], ... E[n] is an arrangement of D[2],
..., D[n], with b[i] denoting the radius of E[i]. Then a[2] >= b[2]
and we may also assume a[3] >= b[3] (otherwise flip and relabel). Now
it is sufficient, by the induction hypothesis, to show that
theta(a[1],a[2]) + theta(a[1],a[3]) - theta(a[2],a[3]) >=
theta(a[1],b[2]) + theta(a[1],b[3]) - theta(a[2],b[3]).
But (1) implies that
theta(a[1],a[2]) + theta(a[1],a[3]) + theta(b[2],b[3]) >=
theta(a[1],a[3]) + theta(a[1],b[2]) + theta(a[2],b[3]),
and this means it is sufficient to prove:
theta(a[1],a[3]) + theta(a[2],b[3]) >=
theta(a[1],b[3]) + theta(a[2],a[3]).
But this too is a consequence of (1).
Note. A similar argument shows that the smallest inner radius occurs
for the configuration:
...D[5]D[n-3]D[3]D[n-1]D[1]D[n]D[2]D[n-2]D[4]....
|
| Anyone remember Bill Gosper ? Or know what he's up to now ?
I worked with him at the AI lab at MIT summers '70 - '74. He was
a fascinating mathematician (and chinese food connoiseur).
He had an interesting display hack on the round 340 display connected
to the pdp6.
When you started it, there would be a several second pause while it
"initialized memory". Then something looking like a telphone dial
would appear. Just drawn in thin white lines on the green phosphor
background. No screen "background" as this was a vector display.
More specifically, the picture was of an inner circle, an outer circle,
and anywhere from 5 to 10 or so circles in a ring, such that each ring
circle touched the inner one, its two ring neigbors, and the outer
circle.
I hope you can imagine how this looks like a phone dial.
Anyway, the inner circle would slowly float from the center towards the
edge of the outer circle. As it did so, the ring of circles would
smoothly change diameters such that they all still touched ! So he for
sure well understood the math involved here.
The inner circle floated to one edge, then slowly back across until it
touched the opposite edge.
Then it kept oscillating back and forth, with the ring circles of
course continuing to adjust smoothly so that they always just fit !
Gradually, the inner circle oscillated faster and faster, until some
sort of strobe effect took over and at this point some stationary
circles stood out in the flutter.
My guess is that the initial memory "initialization" was that memory
was filled with the display lists describing all possible needed circle
sizes. I'd love to see the source code for that program.
Remember(!), the 340 display was a vector display, and all you could
really tell it was display lists with simple commands such as
I am an x coordinate
I am a y coordinate
reset
...
Gosper always had interesting stuff. Ask me some time about the puffer
train whose smoke consisted of glider guns.
/Eric
|
| Gosper was written up in a book "More Mathematical People", I think
there were a bunch of other well known names in there such as Don Knuth.
I've seen the book for sale in Boston area bookstores, it contained
basically interviews and biographical sketches.
His circle hack can be done easily in terms of fractional linear
transformations of the complex plane that preserve the unit circle.
These transformations of the form
w(z) = (a z + b)/(c z + d), a,b,c,w,z complex
map circles to circles, preserving any incidence relations in much
the same way that projective transformations of the plane map lines
to lines, preserving their incidences. In fact, fractional linear
transformations can even be looked at as projective transformations
of 3 space (represented by 4 by 4 matrices, something common in 3D
computer graphics) that preserve the unit sphere.
This is because:
stereographic projection of the plane to the sphere maps circles
to circles
circles on the sphere can be thought of as the intersection of
a plane with the sphere
projective transformations map planes to planes
choosing projective transformations that also happen to map the
unit sphere to itself gives you the equivalence. It leads to
a kind of orthogonality relation on the matrix.
Another way to see this is to write the equation for a circle in the
complex plane with center z0, radius r, as a Hermitian matrix form
| z* | | 1 -z0 | | z |
| | | | | | = 0 z* = complex conjugate
| 1 | | -z0* (z0 z0* - r^2) | | 1 |
If you transform the vector (z, 1) via a 2 by 2 complex matrix
and its complex conjugate transpose on both sides of this equation, you
again get a Hermitian matrix and you can identify the center and
radius. [A Hermitian matrix is equal to the conjugate of its transpose]
So, basically, you can define a whole host of interesting transformations
that map arrangements of circles to other similar arrangements with
very simple programming and without a lot of ad-hoc geometry.
Yet another way to think of this is as resulting from successive
inversions of the plane with respect to circles; generic fractional
linear transformations can be done in terms of even numbers of inversions.
(A line in the plane is a degenerate circle with one point on the circle
at infinity...)
There are some ways to use quaternsions in this area too.
Finally, since continued fractions can be thought of as sequences
of fractional linear transformations, you can see a possible connection
with Gosper's interest in continued fractions.
- Jim
|