2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7  След.
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение23.04.2017, 19:58 
Аватара пользователя


14/12/14
27
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.

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение23.04.2017, 20:35 


18/11/10
75
Yes, please post it here.

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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение23.04.2017, 21:03 
Аватара пользователя


14/12/14
27
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.

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение23.04.2017, 23:31 
Аватара пользователя


14/12/14
27
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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение24.04.2017, 22:29 


24/04/17
5
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!

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение25.04.2017, 03:36 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Great work guys! Pity that Al has kicked you out - it is not fair.

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение25.04.2017, 10:57 


20/01/13
62
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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение25.04.2017, 12:05 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
So do you feel that the Pick's bound can be achieved for any problem size?

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение25.04.2017, 12:54 


25/04/17
3
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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение25.04.2017, 14:39 
Аватара пользователя


14/12/14
27
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.

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение25.04.2017, 23:38 
Аватара пользователя


25/08/12
171
Germany
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.

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение25.04.2017, 23:44 


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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение26.04.2017, 02:11 


24/04/17
5
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

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение26.04.2017, 02:39 
Аватара пользователя


25/08/12
171
Germany
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.

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение26.04.2017, 05:51 
Аватара пользователя


14/12/14
27
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.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 102 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group