hihi, all - Minimum area convex Z^2 lattice polygons (methods, not results): Longish - If you don't particularly care about this problem, you can delete this message now. It will be posted and explained on the web later anyway. Looking for minimal area, I decided that I could prove that there are no lattice points on the interior of any edge (so the only perimeter lattice points are vertices, i.e., corners). A \ \ B \ \ C | | D (replacing ABCD with ABD stays convex and gets smaller area) I also decided that I could prove that we can start by taking the first point to be the origin and insisting that the first point after the origin must be in the first quadrant, and that all the points are in the upper half-plane. (various translations and rotations can acheive this property) Now the program just uses a simple radius bounded backtracking search for the points in the polygon, with some special processing near the end. At each stage after the origin point, there is a wedge of the lattice that contains candidate lattice points, defined by lower and upper bounding half-lines. The lower bound of the wedge is the line to the previous point from the previous but one point (except when finding the second point, when the line is the positive horizontal axis). The upper bound of the wedge is the line from the previous point to the origin (except when finding the second point, when the line is the positive vertical axis). I think I'll make a couple of postscript pictures and put them where they can be downloaded, to make this description clearer (in addition to the answers and the polygons). The program enumerates lattice points in a simple spiral out to the chosen radius bound, and checks them for wedge membership. Because the polygons are so small, I can use a simple recursive function for the search, and that way the backtracking is entirely managed by the function calls (it helps that the spiral enumeration can be done incrementally, that is, each point in the spiral can be computed from just the previous one). I ran a profile on the program, and it spends over 90% of its time in the function that chooses the next point in the wedge, so that is where time improvements will be most useful. Incidentally, the counts that I posted for the number of minimum area polygons (with each edge length bound) may be incorrect, since I forgot to make the program check the length of the last edge (from the last polygon point chosen to the origin), so the counts may be large by a few. They are right, though, for the few larger polygons I re-checked. I will correct the counts for the rest of the sizes once the new search strategy is fast enough. Dylan Thurston asked about removing SL(2,Z) symmetries, and I am still thinking about that. It should be clear that the program I wrote provides little or no help along those lines, and that a separate program should be written for that problem, using the polygons output by the original search. I am trying to think about that, too (I will make all the polygons available). I thank all of you who sent questions and suggestions about the problem, and I welcome any suggestions for improving the spiral enumeration, improving the wedge enumeration to eliminate the spiral enumeration, and / or organizing the SL(2,Z) program. Some theoretical upper bounds on the minimum perimeter (or maximum edge length) of a minimum area (convex lattice) polygon would help if they were small enough, because that would bound the search usefully. ====