Al Zimmermann - Polygonal Areas

[yae9911]

Markus Sigg, Hermann Jurksch and myself have found a few improved solutions after the contest. Since Al Zimmermann has decided to delete them from his webpage, I'd like to show the solutions here in the forum, using the Javascript-based Polygon Browser written by Markus Sigg. Of course, the browser can be applied to visualize any other solution.

We have found two solutions for the minimum problem achieving the Pick bound:
113:55.5, found April 9, 2017
and
131:64.5, found April 22, 2017.

I'll also post the other improvements and perhaps an outline of the applied methods, if there is some interest in this group.

[Jarek]

Yes, please post it here.

BTW, why were those solutions removed from the Al's website?

[yae9911]

Al didn't give a reason, but I would guess that he disliked Markus Sigg's announcement in his Yahoo group, that we had already co-operated during the contest. Since I had been expulsed from the contests some time ago, doing joint work with me seems to be considered as being infectious. In fact, Al has eliminated Markus Sigg and his post-contest contributions from all previous result pages.

For the improved polygons I have to check our records, because we understandably didn't expect that they might become lost on the contest page.

[yae9911]

Here are the other deleted post-contest records. None of them achieves the Pick bounds N/2-1 for the "min" and N^2-4.5*(N-1) for the "max" polygons.

419 max, no other post contest result: 419 max:173668.5 found 2017 Apr 2
373 min, improves Mitsu Itakura's post contest 194.5: 373 min:191.0 found 2017 Apr 14, based on Tom Sirgedas' contest result
521 max, no other post contest result: 521 max:269091.5 found 2017 Mar 29
419 min, improves Mitsu Itakura's post contest result 216.5: 419 min:216.0 found 2017 Mar 20
257 min, improves Tomas Rokicki's contest result: 257min:132 found 2017 Mar 13, starting from TR's contest result 223 min

[TomSirgedas]

Nice work!

I updated the post-contest improvement spreadsheet here: https://docs.google.com/spreadsheets/d/ ... sp=sharing

I'm impressed by the modification to my 373 min, very clever!

[dimkadimon]

Great work guys! Pity that Al has kicked you out - it is not fair.

[jcmeyrignac]

I'm using a similar approach, by mutating the best solutions.

If you are interested, I have a collection of the best mutated solutions.
Here are my 120 solutions to Min373: http://euler.free.fr/min373.txt

[dimkadimon]

So do you feel that the Pick's bound can be achieved for any problem size?

[Alex1a]

dimkadimon в сообщении #1212408 писал(а):

Great work guys! Pity that Al has kicked you out - it is not fair.

Yes, great work! Also Markus solution viewer is really great, don't oversee it :)

My placement changed from 5. to 4. and it doesn't feel right...

Moritz

[yae9911]

dimkadimon в сообщении #1212436 писал(а):

So do you feel that the Pick's bound can be achieved for any problem size?

For large N: Yes. The solution space is huge. For the minimum area problem, N=15 might already be the last N for which no Pick-optimal solution exists. For the maximum area problem this limit might be higher. N=23 is an example where the bound is achieved.

 My best min results
N      Area      # of configs 
 3      1.5      1 
 4      1.0      1 
 5      1.5      1 
 6      4.0      2 
 7      4.5      3 ? 
 8      3.5      4 ? 
 9      4.5      1 
 10      4.0      1 
 11      5.5      1 or 2 
 12      6.0      7 ? 
 13      6.0      7 ? 
 14      6.5      ? 
 15      7.0      ? 
 16      7.0      ? 
 17      7.5      ? 
 18      8.0      ? 
 19      8.5      ? 
 20      9.0      ? 
 21      9.5      ? 
 22      10       ? 
 23      10.5      ? 

Can someone (Herbert?) try to verify the following table?

My best max results
N      Area      # of configs 
 3      1.5      1 
 4      4.0      1 
 5      9.0      1 
 6      14.0      2 
 7      22.0      1 
 8      32.5      1 
 9      44.0      1 
 10      59.0      3 
 11      75.5      >=2 
 12      94.5      1 
 13      113.0      ? 
 14      136.0      >=2 
 15      161.5      ? 
 16      187.5      ? 
 17      216.5      1 
 18      246.5      ? 
 19      279      ? 
 20      313.5      ? 
 21      350.5      ? 
 22      389.0      ? 
 23      430      ? 

I am planning to submit corresponding OEIS sequences, as I have done for almost all of the more recent AZP contests.

[Herbert Kociemba]

yae9911 в сообщении #1212458 писал(а):

Can someone (Herbert?) try to verify the following table?

For the maxima I get the same for N=3...8. But for N=9 I get two optimal configs:
(1,2), (7,1), (9,3), (8,9), (3,7), (6,5), (4,6), (5,4), (2,8) and
(1,2), (7,1), (9,5), (8,9), (3,8), (6,3), (5,4), (4,6), (2,7)

N=10 is running and I will tell the result soon. We will see if it is it possible within a reasonable time to do a complete search for N=11. The program is not optimized for the search of maxima but just a dumb generator of all possible configurations.

[TomSirgedas]

all mins for 5 to 20:
https://pastebin.com/gE8azmB4

[TomSirgedas]

For max, the hull can have different shapes. Here's my output for 2 of the possible hull shapes:
"hull3" = https://pastebin.com/wqmM4nsd
"hull4" = https://pastebin.com/v6k6vSv8

Here's some c++ code to generate this output if it's useful:
https://pastebin.com/LbgwAAbh

[Herbert Kociemba]

Herbert Kociemba в сообщении #1212584 писал(а):

For the maxima I get the same for N=3...8. But for N=9 I get two optimal configs:
(1,2), (7,1), (9,3), (8,9), (3,7), (6,5), (4,6), (5,4), (2,8) and
(1,2), (7,1), (9,5), (8,9), (3,8), (6,3), (5,4), (4,6), (2,7)

N=10 is running and I will tell the result soon.

I can confirm your results for N=10.

[yae9911]

For the max 10 problem none of the two hull types considered in Tom's lists produces the optimum.
Example hull type 3: 10:56
Example hull type 4: 10:57
My best result: 10:59

For the other max problems I've seen one improvement against my table, which is for N=16:
Hull type 4: 16:188.5

Hull type 4 seems to win for all larger N.