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