To:asimov@nas.nasa.govSubject:Largest Equilateral Triangle Inside of Square TorusDate:Tue, 05 Mar 1996 16:58:05 -0800From: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.govSubject:Largest Equilateral Triangle Inside of Square TorusDate:Wed, 06 Mar 1996 09:46:35 -0800From: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 jstFrom:Pat_Ballew_at_~~MISA-FHS@ccmail.pac.odedodea.eduTo:eppstein@ics.uci.eduSubject: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.EDUTo:Pat_Ballew_at_~~MISA-FHS@ccmail.pac.odedodea.eduSubject:...continuedDate: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 jstFrom:Pat_Ballew_at_~~MISA-FHS@ccmail.pac.odedodea.eduTo:eppstein@ICS.UCI.EDUSubject: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.EDUTo:Pat_Ballew_at_~~MISA-FHS@ccmail.pac.odedodea.eduSubject:Re: ...continuedDate: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/