To: asimov@nas.nasa.gov
Subject: Largest Equilateral Triangle Inside of Square Torus
Date: Tue, 05 Mar 1996 16:58:05 -0800
From: David Eppstein <eppstein@ICS.UCI.EDU>
Did you ever get any answer to your message last October with this
title, asking for the largest equilateral triangle that can be placed
without self-intersection in the square torus? I think I have one...
Equivalently, this is asking for the densest packing of the plane
by disjoint equilateral triangles translated to the vertices
of the integer square lattice. There is really only one parameter left
to optimize, the angle of the triangle -- you can grow triangles
with a given angle until they touch each other, giving a function
f(theta) which is the largest square-lattice-packing of equilateral
triangles at angle theta. Actually this is defined only mod 30 degrees
since rotating a triangle by that amount places it in an equivalent position.
It seems from inspection that [in the range 0 < theta < 30]
f(theta) has a unique maximum, at 15 degrees, at which point when you do
the triangle-growing process described above you hit two other triangles
simultanously. I've drawn a picture of the corresponding packing in
http://www.ics.uci.edu/~eppstein/junkyard/tripack.gif and .ps
I haven't gone through a rigorous proof that this is the only answer,
or computed the size of the resulting triangle, but both of these
steps look completely mechanical.
--
David Eppstein UC Irvine Dept. of Information & Computer Science
eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/
To: asimov@nas.nasa.gov
Subject: Largest Equilateral Triangle Inside of Square Torus
Date: Wed, 06 Mar 1996 09:46:35 -0800
From: David Eppstein <eppstein@ICS.UCI.EDU>
Following up on my message of yesterday:
This is asking for the densest packing of the plane
by disjoint equilateral triangles translated to the vertices
of the integer square lattice. There is really only one parameter left
to optimize, the angle of the triangle -- you can grow triangles
with a given angle until they touch each other, giving a function
f(theta) which is the largest square-lattice-packing of equilateral
triangles at angle theta. Actually this is defined only mod 30 degrees.
It seems from inspection that [in the range 0 < theta < 30]
f(theta) has a unique maximum, at 15 degrees.
I now have a nice non-mechanical proof of this.
Given an angle theta, I want to describe how to compute f(theta)
as defined above. Let point A=(0,0), B=(0,1) C=(1,0)
[I'm a computational geometer, I use coordinates.
Everything here can be done in compass & straightedge but who cares.]
Draw lines L1 through A at angle theta, L2 through A at angle theta+60,
L3 through B at angle theta, L4 through C at angle theta+60.
Let D = intersection(L2,L3) and E = intersection(L1,L4).
Then f(theta) = min { distance(A,D), distance(A,E) }.
[You also have to worry about your triangle covering point (1,1)
but that turns out not to be a problem.]
So what does f(theta) look like and where is its maximum?
Let's look at distance(A,D). As theta varies from
0 to 30, angle BDA stays fixed at 60 degrees.
Therefore D traces out a curve of constant angle, namely a circle
in which AB forms a 120-degree chord. From this we can see
that distance(AD) increases monotonically as theta increases from 0 to 30.
Symmetrically distance(AE) decreases monotonically.
Since neither distance has a local maximum in this range,
the maximum of f(theta) occurs where the two are equal,
which by symmetry is at theta=15 degrees.
QED...
I still haven't computed the size of the triangle at that angle,
but it's a simple question of trigonometry:
what's the ratio of hypotenuse to middle side in a 15-60-105 triangle?
--
David Eppstein UC Irvine Dept. of Information & Computer Science
eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/
Date: Fri, 13 Jun 97 07:30:20 jst
From: Pat_Ballew_at_~~MISA-FHS@ccmail.pac.odedodea.edu
To: eppstein@ics.uci.edu
Subject: equilateral triangles and "Geometry Junkyard"
Mr David Eppstein,
I stumbled across your "Geometry Junkyard" and was very pleased to
find such a wealth of great questions and ideas. I was even more
surprised that you had addressed a problem (equilateral triangle
question by Dan Asimov) to which I had made a conjecture. Your note
on the web page indicates that your solution of a triangle with sides
of 2 units corrects a previous attempt. I assume this refers to my
post of 10/26/95 indicating appx 2.15 as a solution. I did, however,
follow up on 10/29/95 with a second statement that improved the
original guess with a general conjecture about ALL triangles, not just
equilateral triangles, and in fact I made a conjecture about *any*
convex polygon, which I now realize was *very* wrong.
Because I almost never have the opportunity to discuss these kinds
of problems with people of your experience, I would love to have you
address the general conjecture I made about a triangle that contains a
unit square in the 10/29/95 post. That would include your solution,
and generalize somewhat, I think. Is it correct in either of the two
parts.
Thanks again for the great source of problems.
Pat Ballew,
Misawa, Japan
From: eppstein@ICS.UCI.EDU
To: Pat_Ballew_at_~~MISA-FHS@ccmail.pac.odedodea.edu
Subject: ...continued
Date: Fri, 13 Jun 1997 10:57:42 -0700
A 45-45-90 triangle with hypotenuse length 3-epsilon contains
a square of side length 3/2sqrt2 ~ 1.06, larger than a unit square;
but this triangle can still be placed to avoid all integer points.
I think this is the maximum possible size for a square contained in a
triangle that avoids the integer points, but have no proof.
I think the other part of your conjecture, that a triangle that doesn't
contain a unit square can avoid all integer points, is true.
Just place the triangle with one side along the x axis (y=0).
Since it doesn't contain the unit square, it in particular doesn't
contain a unit square aligned with the coordinate axes in this placement,
and therefore there is enough room for its top corner to poke between
the integer points on the line y=1.
Would you mind if I include your correspondence in my web site?
--
David Eppstein UC Irvine Dept. of Information & Computer Science
eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/
Date: Mon, 16 Jun 97 09:31:20 jst
From: Pat_Ballew_at_~~MISA-FHS@ccmail.pac.odedodea.edu
To: eppstein@ICS.UCI.EDU
Subject: Re: ...continued
Mr Eppstein,
Thank you for the response. I have tried repeatedly to visualize
an orientation of a 45-90-45 right triangle with even a hypotenuse of
3 which would not touch a lattice point. I even made a physical model
thinking I might be able to see something, but I still can't find the
orientation you must have used. One more clue please!
I have always assumed anything I post to e-mail is, whatever our
intentions, almost public. You may use anything I have ever written
that might help.
Thanks again for the response.. I'll keep twisting that sucker
Pat Ballew
Misawa, Japan
From: eppstein@ICS.UCI.EDU
To: Pat_Ballew_at_~~MISA-FHS@ccmail.pac.odedodea.edu
Subject: Re: ...continued
Date: Mon, 16 Jun 1997 10:26:24 -0700
/ \
o o/ \o o
/ \
/ \
/ \
/_____________________\
o o o o
--
David Eppstein UC Irvine Dept. of Information & Computer Science
eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/
