It's interesting to read of Chris' very long computation to find or count certain figures in discrete geometry. Last year I finished a two-year run (on only one PC) whose purpose was to count figures in discrete geometry, but I was (and am) working with figures of a very different kind, namely topologically distinct polygons as a function of the number of sides n. For n=3,4,5,6,7, I got S(n)=1,2,6,48, and (may not be entirely accurate) 657. Of course this depends entirely on what's meant by "topologically distinct," and I consider two (generally self-crossing) n-gons A and B topologically equivalent if one can be transformed into the other by distortions which cause no points to cross any sides. The long computation (for n=8 and below) was necessitated by the slow method I used to determine whether randomly generated n-gons A and B are really equivalent. I have not published on this because extending the count to n>6 involves some code (in Mathematica) that I haven't finished and because this investigation spills over into several related areas. One way to characterize a given topological type of n-gon, say A, is to restrict its vertices to a square lattice and find the minimum area rectangle that A will fit into. (The area of the n-gon itself is not necessarily well-defined.) Given that Chris ran his code on more than one computer, and that he coded in C, his computation was undoubtedly more fundamentally difficult than mine. But to extend mine even to n=9 would take not just more-optimum code but a fundamentally new approach, unless I had access to a supercomputer. I haven't read Chris' post carefully yet but plan to after I get back from Antarctica in late January. Merry solstice, everyone. Steve Gray Chris Landauer wrote:

subtitle: end of an obsession

Minimum Area Convex Lattice Polygons For 3 <= n <= 128

I am pleased to announce the end (finally!) of my patience (and computing resources) with this problem. I have run programs for the last three years to compute minimum area convex lattice polygons, and I have results for n<=128, with much confidence (but not proofs) for all of them. The following discussion explains my confidence assessment.

The confidence levels are necessary because the problem is not amenable to a simple finite search.

Every SL(2,Z) image of a convex lattice polygon is a convex lattice polygon with the same area, so the search must be artificially limited. Since the SL(2,Z) images have arbitrarily long polygon edges, I chose to use the maximum length of the edges in a polygon as a search limit (it obviously makes the search finite). I used the L1 length to make the computation simple and the lengths integers; Linfinity would produce the same results with slightly different structure. Length always means L1 length here.

The search program found all minimum area convex lattice polygons (just polygons henceforth) with a fixed number n of edges and a strict bound b on the edge length. If the areas of two polygons were equal, it used the one with the smaller perimeter (sum of edge lengths), and of the perimeters were equal, it used the one with the smaller maximum edge length, and if those were equal, it used the one found earlier. This ordering defined the ``best'' polygon with a given number of edges.

The ``margin'' is the difference between the search bound and the maximum edge length of the best polygon. The confidence measure for the results is the margin: margin at least 3 is good, margin 2 or less is worrisome, and margin 1 is the smallest possible (because the edge bound b is a strict bound), so it is completely uninformative.

Margin 2 is worrisome because in several instances, margin 2 results for a given b were superseded by margin 1 results for b+1 (so edge bound b gave the same minimum area as b-1, but the b+1 search found a smaller minimum area). For example, for n=27, b=7, the same minimum area 315.5 is found as for b=6, so the margin is 2, but for b=8, a new smaller area 312.5 is found with maximum edge length 7. The same thing happens for n=29, 31, 33 and other, larger n (mostly odd n). In every one of these cases, the perimeter of the newly found polygon is larger than the old one (though not a lot larger), leading me to think about running the same search but for minimum perimeter polygons (the algorithms would need only a trivial change to the ``best'' ordering).

On the other hand, that peculiarity never happened with margin 3 results. They were not superseded when b was further increased in any of the examples that were run with any of the programs I wrote. The ``much confidence'' written above means that the relevant margins are all at least 5.

Theory

There is a theorem that when n is even, there are minimum area polygons that are centrally symmetric. I observed in many earlier runs that the same is almost true when n is odd, so my programs have assumed that, though I have not proven it.

Therefore, strictly speaking, all of these search results are only upper bounds (since they produce example polygons), but I have much confidence that all of them are exact, as described earlier.

Similarly, if there were also a theorem that said something like ``among the minimum area polygons, there is at least one with a maximum edge length less than B(n)'' for some explicit function B(n) that is not too large, then the same program could be run more definitively.

Algorithms

The algorithms have evolved from a more or less direct simulation of which edge to choose, to a backtracking algorithm that took about two years to run all the cases for b=13 (and many of the smaller cases for b=14), to an incremental dynamic programming approach that ran all earlier cases with search bound b=14 in seven months, to a slight modification of the approach that has run all of the earlier cases and much more (with an even larger search bound b=16) in the last two months on just one machine. This last version is many orders of magnitude faster than the first version I wrote.

Computing

I used 10 of my commodity PCs, most ranging from 3.0GHz to 3.6GHz, and having 4GB of memory and 1TB of disk space (four of them are older 2GHz desktops and two are slow laptops that were used for some of the program development and other experiments). Between 1 and 8 (more than that flipped the circuit breaker in my home) of them have been running continuously (except for power failures) since early December of 2003, when the first math-fun e-mail announced the problem, and that the case n=11 was not yet completely decided (I thought to myself, ``I can do that'').

One of the computers is a dual 3.0GHz G4 Mac running OS X, the older, slower ones run SuSe Linux, and all of the non-Macs run FreeBSD (my favorite version of UNIX). The programs were all written in what I call C-- (my own personal portable subset of C), with identical source code on each system on each machine. The slow machines were perfectly adequate for the smaller searches, but could not manage the data flow, volume or disk activity in the larger ones, and bogged down more than the problem should have required.

I needed to make a change to the operating system kernel before it would correctly report cpu times in excess of about 137 hours (it is a simple 64-bit counter overflow that has apparently been in UNIX since BSD days at Berkeley on the VAXen), but my changes have been working smoothly and accurately for more than three years now. The last versions of the program do not need that change, since they run much faster.

Discussion

The scripts that run the search programs face a difficult space-time tradeoff. The file sizes generated in each of the largest cases I ran are up to 80GB, though the programs only took 20 hours or so to run each case (each different value of the number n of sides). Earlier versions generated much smaller files, but took hundreds or even thousands of cpu hours (and were therefore too often interrupted by power failures and needed to be restarted from the most recent checkpoint; I only reluctantly put the checkpointing and recovery code into the programs because it makes them much more complicated, but I lost two almost 1800cpu hour runs before that).

Extending the search to b=20 is a barrier for now, since the best estimate that I have for the largest of the generated file sizes is well over 10TB (and the margins I already have mean I really only need to run the program with b=20 for the largest n, say 112<=n<=128 to get adequate margins in that range).

I also have timing and progress statistics for almost of the runs of all of the programs on all of the machines, which I have used to make pretty accurate predictions of cpu and elapsed times for the larger cases (so I didn't get too impatient with them), and some preliminary notions of how to improve the simple timing models I used.

**Breaking News**

I just found (18 December) a simplification that makes the program files much smaller (the ratio decreases rapidly as n grows, and the asymptotic ratio appears to be less than 1/60), and therefore the programs can run very much faster and the code can be made much simpler (no checkpointing or complicated sets of intermediate files). I've rewritten all the programs and scripts accordingly, and in the first 6 hours it ran all of the b=20 cases I had run before (up to n=44), and much more.

This program script finished in about 4 days, and produced margins at least 5 for all n up to 128, and was weakly verified by a check run (same program, different area thresholds).

Just to get an alternative view, I did run the minimum perimeter search, and have those results also. The margins are at least 9 for all n<=128, and the corresponding areas are within a few percent of the computed minimum areas in all cases. This leads to the notion that pretty good upper bounds for the minimum area for much larger n can be obtained relatively cheaply using the minimum perimeter search, since for all n <= 128, we only need to use edge bound 12 to find them, and slightly larger edge bounds to get reasonable margins.

It is also curious that for all n up to 20, and several more up to and including n=43, the minimum area polygon is also a minimum perimeter one, since it does not happen for any larger n (and I did not expect it to happen as much as it did).

b=20 results

all lengths are L1-lengths ||(x, y)|| = |x| + |y|

min perim polygon has minimum perimeter, and minimum area among those with the minimum perimeter, and minimum maximum edge length among those with the minimum perimeter and area

min area polygon has minimum area, and minimum perimeter among those with the minimum area, and minimum maximum edge length among those with the minimum area and perimeter

min perim polygon min area polygon (if different) min max min max n area perim edge area perim edge 03 0.5 4 02 04 1 4 01 05 2.5 8 02 06 3 8 02 07 6.5 12 03 08 7 12 02 09 10.5 16 03 10 14 18 03 11 21.5 22 03 12 24 24 03 13 32.5 28 04 14 40 30 03 15 51.5 34 04 16 59 36 03 17 75.5 42 05 18 87 44 04 19 106.5 50 05 20 121 52 04 21 149.5 58 05 144.5 60 05 22 167 60 04 164 62 05 23 193.5 66 05 24 219 68 04 210 72 05 25 252.5 74 05 248.5 76 05 26 280 78 05 274 80 05 27 318.5 84 05 312.5 88 07 28 346 88 05 345 90 05 29 394.5 94 05 391.5 96 07 30 430 98 05 31 485.5 104 05 483.5 106 07 32 523 108 05 33 589.5 114 05 588.5 120 07 34 632 118 05 35 704.5 124 06 36 749 128 05 37 844.5 134 06 835.5 136 07 38 890 138 05 39 994.5 144 06 977.5 146 07 40 1039 148 05 41 1139.5 156 07 42 1225 160 06 1222 162 07 43 1325.5 168 07 44 1421 172 06 1412 176 07 45 1540.5 180 07 1525.5 182 07 46 1657 184 06 1620 192 07 47 1764.5 192 07 1746.5 196 07 48 1903 196 06 1838 208 08 49 2027.5 204 07 1984.5 212 08 50 2156 210 07 2088 218 08 51 2287.5 218 07 2244.5 228 09 52 2416 224 07 2357 234 08 53 2561.5 232 07 2522.5 246 09 54 2702 238 07 2651 244 08 55 2868.5 246 07 2811.5 258 09 56 3009 252 07 2953 260 08 57 3198.5 260 07 3121.5 276 09 58 3360 266 07 3278 278 09 59 3545.5 274 08 3495.5 282 09 60 3717 280 07 3612 296 09 61 3925.5 288 08 3865.5 302 09 62 4102 294 07 4020 308 09 63 4326.5 302 08 4239.5 320 11 64 4507 308 07 4439 322 09 65 4756.5 316 08 4682.5 332 11 66 4970 322 07 4902 334 09 67 5231.5 330 08 5156.5 346 11 68 5445 336 07 5387 348 09 69 5730.5 344 08 5661.5 368 11 70 5980 350 07 5898 362 09 71 6277.5 358 08 6179.5 368 09 72 6527 364 07 6418 376 09 73 6772.5 374 08 6729.5 382 09 74 7065 380 08 6974 390 09 75 7327.5 390 08 7307.5 394 09 76 7619 396 08 7557 404 09 77 7942.5 406 09 7905.5 408 09 78 8221 412 08 8182 420 09 79 8578.5 422 09 8536.5 426 09 80 8839 428 08 8835 434 09 81 9255.5 438 09 9215.5 442 09 82 9589 444 08 9512 450 09 83 9985.5 454 09 9916.5 458 09 84 10353 460 08 10218 464 09 85 10725.5 470 09 10660.5 474 09 86 11201 476 08 10984 482 09 87 11562.5 486 09 11450.5 492 10 88 12063 492 08 11759 500 09 89 12577.5 502 09 12263.5 510 10 90 12874 510 09 12635 516 09 91 13294.5 520 09 13141.5 528 11 92 13694 528 09 13525 532 09 93 14155.5 538 09 14052.5 546 11 94 14586 546 09 14448 550 09 95 15115.5 556 09 14996.5 562 10 96 15487 564 09 15399 568 09 97 16052.5 574 09 15979.5 578 11 98 16508 582 09 16415 588 10 99 17089.5 592 10 17009.5 602 11 100 17557 600 09 17473 608 10 101 18173.5 610 10 18072.5 624 11 102 18676 618 09 18570 626 10 103 19320.5 628 10 19171.5 638 11 104 19823 636 09 19683 644 10 105 20528.5 646 10 20346.5 660 11 106 21096 654 09 20896 666 11 107 21812.5 664 10 21563.5 682 11 108 22385 672 09 22134 688 11 109 23181.5 682 10 22828.5 706 12 110 23786 690 09 23404 710 11 111 24636.5 700 10 24120.5 722 11 112 25203 708 09 24743 730 11 113 25869.5 720 11 25456.5 776 13 114 26575 728 10 26103 752 11 115 27241.5 740 11 26826.5 798 13 116 27987 748 10 27500 808 13 117 28680.5 760 11 28245.5 824 13 118 29459 768 10 28958 830 13 119 30192.5 780 11 29790.5 840 13 120 30971 788 10 30432 856 13 121 31882.5 800 11 31322.5 858 13 122 32745 808 10 32038 872 13 123 33489.5 820 11 32869.5 888 15 124 34537 828 10 33659 890 13 125 35330.5 840 11 34538.5 904 15 126 36473 848 10 35367 908 13 127 37217.5 860 11 36264.5 922 15 128 38427 868 10 37095 904 11

end of file results-b20perim.txt

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun