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