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