[math-fun] Re: small area convex lattice polygons
Dan Hoey wrote:
Chris Landauer wrote:
well, the systematic search program i wrote to find minimum area convex lattice polygons took 20 hours for n=20 and 80 for n=21, with results as follows....
My understanding is that this still does not establish a lower bound on area even for the 11-gon, unless we can somehow prove that there is a minimum-area 11-gon with no edge more than 10 units long. Given the use of SL(2,Z) to force a unit edge, we would have to prove the existence of an 11-gon with a unit edge _and_ no edge longer than 10. ...
This is of course true. I am merely encouraged by the fact that for small n, the minimum area did not decrease when the edge bound was increased from some very small value up to 50. In fact, in the higher cases (with the random search program), the minimum area found decreased substantially as the edge length bound decreased, until a threshold was passed and no polygons could be completed at all. Similary, I noticed that among all of the minimum area polygons that my program found for even n, all of them were centrally symmetric (that is, the second half edge directions are the negatives of the first half ones). I think that there is a simple proof of this (perhaps less cryptic and subscripty than the one in Barany and Tokushiga), and I am presently writing the code to use this observation in a different systematic search program. Finally, I haven't figured out anything that can usefully bound the perimeter or the maximum edge length of these polygons, but it seems that most values of n<=21 have many long skinny minimum area polygons and a few more blobby ones (which are the ones that should have smaller diameters). Oh, and by the way, the maximum euclidean distance and the maximum manhattan distance between two vertices of any of the minimum area polygons my systematic search program found occur between the same pairs of vertices (I just checked that). more later, cal Chris Landauer Aerospace Integration Science Center The Aerospace Corporation cal@aero.org
On Tue, Jan 06, 2004 at 04:31:27PM -0800, Chris Landauer wrote:
Finally, I haven't figured out anything that can usefully bound the perimeter or the maximum edge length of these polygons, but it seems that most values of n<=21 have many long skinny minimum area polygons and a few more blobby ones (which are the ones that should have smaller diameters).
How are you normalizing for the action of SL(2,Z)? Via an appropriate element of SL(2,Z), I would expect that you could make most of those long, skinny shapes look round and blobby. Peace, Dylan
On Jan 7, 2004, at 3:56 PM, Dylan Thurston wrote:
On Tue, Jan 06, 2004 at 04:31:27PM -0800, Chris Landauer wrote:
Finally, I haven't figured out anything that can usefully bound the perimeter or the maximum edge length of these polygons, but it seems that most values of n<=21 have many long skinny minimum area polygons and a few more blobby ones (which are the ones that should have smaller diameters).
How are you normalizing for the action of SL(2,Z)? Via an appropriate element of SL(2,Z), I would expect that you could make most of those long, skinny shapes look round and blobby. I somewhat doubt this. A filled convex polygon is associated with a unique filled ellipse with the same center of mass and second moments. Up to translation and scaling, there is a 2-dimensional family of ellipses (depending on the slope of the major axis and the eccentricity.) This family is otherwise known as the hyperbolic plane. The action of SL(2,Z) on the hyperbolic plane has a non-compact quotient, and I don't see why one should expect the answers to stay in a compact portion. It would be interesting to see a scatter-plot of the optimal answers. One way to do this would be to fit the ellipse (this is straightforward), normalize by scaling so that the product of major and minor axis lengths is 1, then transform by SL(2,Z) to make the major axis minimal. Plot the topmost end point of the major axis, which is a point in the upper half plane. There are discussions of this action lots of places, and it's easy to do the normalization under SL(2,Z). Limiting the answers to a compact portion of this quotient space is tantamount to bounding the search.
Another strategy that would probably be revealing and perhaps algorithmically efficient would be to use some description of polygons that is invariant by SL(2,Z). One way to do it: (a) for each edge in the polygon, how many lattice points does it intersect, excluding end points? [is this ever more than 0?] (b) Each pair of successive edges defines two vectors that give a coordinate system for the plane. What are the coordinates of the vector for the following edge, in this coordinate system? This information, (a) and (b) for each edge, is redundant, i.e. it is subject to a bunch of equations, but at least it's invariant. Probably the (a) conditions are not needed. From the (b) conditions you get a sequence of matrices that transform between the successive coordinate systems --- the product of all of them must be the identity. Perhaps better, a related invariant description can be given by (1) the areas of the triangles spanned by any 3 successive vertices, and (2) the areas of the quadrilaterals spanned by any 4 successive vertices. This is a sequence of 2n integers, 3 too many --- the 3 consistency conditions can again be expressed by a matrix product that has to be the identity. Bill Thurston
Chris Landauer wrote:
... i still can't figure out what B&T mean by ``the minimizing polygon'', so i have no useful comment about that paper yet.
Oops! I forgot to send this reply I wrote to Bill Thurston's note on Thursday. It has some explanation that may help you understand B&T. Bill Thurston wrote:
Another strategy that would probably be revealing and perhaps algorithmically efficient would be to use some description of polygons that is invariant by SL(2,Z).
Amen, brother.
One way to do it: (a) for each edge in the polygon, how many lattice points does it intersect, excluding end points? [is this ever more than 0?]
No, not for minimal-area polygons.
(b) Each pair of successive edges defines two vectors that give a coordinate system for the plane. What are the coordinates of the vector for the following edge, in this coordinate system?
Neat, though I think they might not always be integers. Maybe that's not so important.
Perhaps better, a related invariant description can be given by (1) the areas of the triangles spanned by any 3 successive vertices, and (2) the areas of the quadrilaterals spanned by any 4 successive vertices. This is a sequence of 2n integers, 3 too many --- the 3 consistency conditions can again be expressed by a matrix product that has to be the identity.
At least these will be half-integers. Here's another approach I got from the Barany&Tokushiga paper ( http://www.renyi.hu/~barany/cikkek/hide.ps -- sorry for the earlier bogus URL ). They take the convex hull C of the edge vectors. They make the important observation that for even n the set V(C) = { (a,b) in C intersect Z^2 : gcd(a,b)=1 } must be exactly the set of edges of the polygon, because otherwise we could replace a pair of vertices of C with the internal primitive pair, giving a smaller area. The problem I had yesterday was that they gave a stealth definition of A(C) = 1/8 sum sum | det(t,u) | t in V(C) u in V(C) which turns out to be the area of the original polygon (by saying a "stealth definition" I mean they didn't say it was a definition, it was just the first use of A(set). I can't complain, I do it myself, usually regrettably.) Anyway, the polygon C has only O(sqrt(n)) vertices, so it's a big improvement. Also, it handles the translation invariance. They deal with SL(2,Z) by taking the "lattice width" of C in the (0,1) direction. They don't define lattice width (citing Kanann&Lovasz in Ann. Math. 128 (1988) 577-602). Not having that, I think this just says to map C to minimize "delta x", though any better insight would be appreciated. Unfortunately, for odd n the convex hull of the edge vectors can include unused primitive vectors. The best I've been able to do for a normal form for that is to take the convex hull of the edge vectors with their negatives, and attach a list of unused primitive vectors. More later, Dan
participants (4)
-
Chris Landauer -
Dan Hoey -
dpt＠exoskeleton.math.harvard.edu -
William P. Thurston