Al Zimmermann - Polygonal Areas

[Alex1a]

Wow, really great work Hugo and Markus. I wish I had more time :)

[yae9911]

Most recent improvements:

Min 521: 263.5

Min 467: 239.0

This doesn't leave too many of the "AZ approved" records untouched.

Current status:


Hugo Pfoertner

[MichaelC]

My exhaustive search for minimum for 12 has completed
The number of unique solutions with area = 6 is 10
This does not agree with the processing of Tom's results which gave 12
When I processed those results, I assumed they were all valid and just removed symmetries

But these two solutions on Tom's list are not valid as they contain intersection (1,4) to (11,11) with (8,9) to (10,10)
(1,4), (11,11), (8,9), (10,10), (3,2), (5,5), (6,6), (7,8), (2,1), (9,7), (4,3), (12,12),
(1,4), (11,11), (8,9), (10,10), (3,2), (6,6), (5,5), (7,8), (2,1), (9,7), (4,3), (12,12),

The 10 minimum solutions for 12 are
(1,1), (2,2), (5,8), (4,5), (8,12), (3,3), (11,10), (6,6), (12,11), (9,7), (7,4), (10,9),
(1,1), (2,2), (7,10), (4,5), (9,11), (6,7), (10,12), (3,3), (5,4), (12,9), (8,6), (11,8),
(1,1), (6,7), (2,2), (7,6), (11,9), (4,4), (12,11), (5,5), (8,8), (9,10), (3,3), (10,12),
(1,1), (6,7), (2,2), (11,9), (7,6), (4,4), (12,11), (5,5), (8,8), (9,10), (3,3), (10,12),
(1,1), (6,8), (2,2), (9,11), (3,3), (11,12), (5,5), (10,9), (4,4), (7,6), (8,7), (12,10),
(1,1), (7,9), (5,6), (9,11), (2,2), (11,12), (4,4), (8,7), (3,3), (6,5), (12,10), (10,8),
(1,1), (8,9), (9,10), (3,5), (11,12), (6,6), (10,11), (2,2), (4,3), (7,7), (5,4), (12,8),
(1,1), (8,9), (9,10), (3,5), (11,12), (7,7), (10,11), (2,2), (4,3), (6,6), (5,4), (12,8),
(1,2), (3,3), (9,10), (5,5), (6,6), (11,12), (8,8), (12,11), (7,7), (10,9), (4,4), (2,1),
(1,2), (3,3), (9,10), (6,6), (11,12), (7,7), (8,8), (12,11), (5,5), (10,9), (4,4), (2,1),


I checked Tom's results for grids 13 to 20 to ensure all the solutions given are valid
They are. So those numbers of minimums obtained from the results do not change

It would take too long to do an exhaustive search for grid > 12 on my computer.

I am still waiting for the exhaustive search for maximum for 12 to complete - so far only one solution found.

[yae9911]

Michael,

thanks for pointing out the wrong number of solutions for min 12. I have thrown the collection of our own min 12 solutions, the purged set from Tom and your 10 solutions into my own solution normalizer, which doesn't eliminate symmetric pairs, and after sorting 20 unique solutions remained. This confirms your findings. I have therefore made a correction to A288248, which now shows a(12)=10.

For the max problems, Tom's program omits some of the possible choices to select the outer hull, as long as the hull is not of the optimal type with one cut corner situated on the other end of the diagonal starting at the "entrance door". So the numbers of max configs shown in A288250 are based on our own searches combined with Tom's results. We have a "framing" utility program that takes an inner small area polygon as input and then uses exhaustive backtracking to build all legal hulls of the maximum possible area by trying all cutting locations around the perimeter of the inner polygon. It finds all possible solutions, but the maximum number of added outer points practically is 7. Adding 8 or even more points is not feasible in reasonable computing time.

For use in the OEIS sequences I have created two catalogs of solution pictures for N<=12:
http://www.randomwalk.de/dxdy/Min_Poly.pdf
http://www.randomwalk.de/dxdy/Max_Poly.pdf.

And, last but not least, we have found a further improvement for the Min 467 problem of the former contest:

467:237.5

[MichaelC]

My exhaustive search for maximum for 12 has finished - only one solution of 94.5

(1,2), (2,10), (4,9), (8,4), (7,6), (6,7), (9,5), (5,8), (3,11), (11,12), (12,3), (10,1),

[yae9911]

New record for max 331:
331:108067.5

I have now also updated Tom's poly area spreadsheet in Google docs.

[yae9911]

Another improvement of the min 467 result:
467:236.5
As mentioned earlier, the structure of solutions where the polygon is squeezed into a narrow region along the diagonal can be explored by using the "shear" option of Markus Sigg's polygon viewer:

[jcmeyrignac]

I'm trying right now to optimize Min419.
My program was able to find 737 solutions from the one published here.

In fact, my program is able to mutate solutions, until an improvement appears.

Where is the list of the solutions for the sequence:
http://oeis.org/A288248
?

I can try to mutate the solutions to get new ones.

BTW, I was able to improve two results of the Delacorte's contest.

[yae9911]

jcmeyrignac в сообщении #1225392 писал(а):

I'm trying right now to optimize Min419.
My program was able to find 737 solutions from the one published here.

Due to the regular structure of solutions that are based on Mitsu Itakura's polygons, it is quite common that many slightly modified solutions with equal area exist. I've found that those almost never help finding improvements. Markus Sigg's breadth first searcher puts already visited solutions into a very large hash table organized as a bit array, after they had a chance to generate successors in the search tree.

Цитата:

Where is the list of the solutions for the sequence:
http://oeis.org/A288248 ?

Earlier in this thread, Tom Sirgedas has posted links to results of his exhaustive search and also to the used C++ program. I'm planning to attach the solutions for small n to the OEIS sequence itself.

Цитата:

I can try to mutate the solutions to get new ones.

This would be surprising, because I have already merged Tom's result with long list of own solutions, and nothing new has shown up.

Цитата:

BTW, I was able to improve two results of the Delacorte's contest.

Not having looked yet, I would expect, that it were those, where Al Zimmerman has removed the submissions by Markus Sigg, which we had jointly found in a long series of improvement rounds. Since neither me nor Markus are allowed to submit post contest results, I'll show the deleted solutions in the Delacorte thread here in dxdy.

News from the ongoing effort to eventually break all (not yet optimal) contest and post contest records for the polygons:
Tomas Rokicki's record for Max 293 has been improved significantly (area increased by 3):
Max293:84530

[yae9911]

We have found some further improvements:
Max223:48724
Max191:35623.5
Max419:173670.5

[yae9911]

Two significant improvements found recently:
Min419:212
and
Min257:129

[dimkadimon]

Hugo and Markus, great work. You should add your pdf files to the OEIS sequences.

Pity you are not competing in the latest competition (Primorial Soup). Perhaps you can still do it informally - feel free to write in the other thread dedicated to it.