[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1957.0. "Crux Mathematicorum 2006" by RUSURE::EDP (Always mount a scratch monkey.) Thu Mar 23 1995 13:11

    Proposed by John Duncan, University of Arkansas, Fayetteville; Dan
    Velleman, Amherst College, Amherst, Massachusetts; and Stan Wagon,
    Macalester College, St. Paul, Minnesota.
    
    Suppose we are given n >= 3 disks, of radii a1 >= a2 >= ... >= an.  We
    wish to place them in some order around an interior disk so that each
    given disk touches the interior disk and its two immediate neighbors. 
    If the given disks are of widely different sizes (such as 100, 100,
    100, 100, 1), we allow a disk to overlap other given disks that are not
    immediate neighbors.  In what order should the given disks be arranged
    so as to maximize the radius of the interior disk?  [Editor's note. 
    Readers may assume that for any ordering of the given disks the
    configuration of the problem exists and that the radius of the interior
    disk is unique, though, as the proposers point out, this requires a
    proof (which they supply).]
T.RTitleUserPersonal
Name
DateLines
1957.1RUSURE::EDPAlways mount a scratch monkey.Wed Feb 21 1996 12:0393
    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]....
1957.2HANNAH::OSMANsee HANNAH::IGLOO$:[OSMAN]ERIC.VT240Wed Feb 21 1996 13:2154
    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
1957.3RUSURE::EDPAlways mount a scratch monkey.Thu Feb 22 1996 11:2612
    Dan D'Eramo has pointed out to me that f[1,2](x,y), where I write
    "[1,2]" to indicate what would normally be subscripts 1 and 2,
    represents the partial derivatives with respect to the first and then
    the second arguments of the function, not the reverse as I suggested in
    .1.  For well-behaved functions, these are the same.
    
    
    				-- edp
    
    
Public key fingerprint:  8e ad 63 61 ba 0c 26 86  32 0a 7d 28 db e7 6f 75
To find PGP, read note 2688.4 in Humane::IBMPC_Shareware.
1957.4Re: Gospers circle hackTDCIS3::ROTHGeometry is the real life!Fri Feb 23 1996 13:4261
   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