2014 dxdy logo

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

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





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


01/06/12
772
Adelaide, Australia
Here are some 13 max:

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

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


14/12/14
26
None of your 3 examples has one of the "standard" frames used in Tom's lists of results for hull3, e.g. 13:113, whereas yours are (rotated to support visual comparison):
13:113
13:113
13:113
So the task of finding all solutions for the max problems is not so easy. Using Markus Sigg's breadth first search (which has no guarantee of finding all solutions) I've found 27 configs with area 113, which include mirrored solutions.
The max 13 might have at least 14 essentially different optimal configs. Definitely not mature enough for inclusion into an OEIS sequence.

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


01/06/12
772
Adelaide, Australia
yae9911 в сообщении #1212638 писал(а):
Definitely not mature enough for inclusion into an OEIS sequence

You can have the sequence go up to n=12 and add the "more" keyword. Or you can use "-1" to mean "don't know" and continue it for further n.

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


24/04/17
5
Each hull shape has a "quality": how close to the theoretical bound it can come. "hull4" has a quality of 0, but others hulls have quality of -1.5, and so on. When you're searching for an area equal to the theoretical bound, you must have a hull quality of 0, and there are only a few of these. When you're searching for slightly less area, there are more hull shapes to consider. (When you're searching for much less area, you'll need to consider hulls with more than one "cavern" carved into them (probably won't be a factor)).

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


01/06/12
772
Adelaide, Australia
TomSirgedas в сообщении #1212659 писал(а):
"hull4" has a quality of 0, but others hulls have quality of -1.5, and so on. When you're searching for an area equal to the theoretical bound, you must have a hull quality of 0, and there are only a few of these

So here is what confuses me: some of your results for hull4 are below optimal (or best found), so how is that possible if hull4 guarantees optimality? Or does it mean that you weren't able to find the best hull4 solution?

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение27.04.2017, 19:36 


24/04/17
5
hull4 doesn't guarantee optimality. But if you start with this shape: http://antiton.de/PolygonalAreas/index.html?(3,2),(4,4),(2,3),(1,9),(8,10),(10,8),(9,1) and "grow" the polygon by only adding triangles with area .5, you'll have an optimal solution, like this:

Изображение

Sometimes the task is impossible, and triangles with larger area are necessary. And/or a sub-optimal starting point like http://antiton.de/PolygonalAreas/index.html?(3,2),(6,6),(2,3),(1,9),(8,10),(10,8),(9,1) can be used.

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


01/06/12
772
Adelaide, Australia
Some optimal max results:

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

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

14:146
(9,10),(7,7),(4,5),(10,12),(2,3),(1,13),(13,14),(14,2),(5,1),(3,4),(11,9),(6,6),(12,11),(8,8)
(5,9),(8,4),(4,10),(9,7),(10,6),(6,11),(13,3),(14,13),(3,14),(1,12),(2,1),(12,2),(11,5),(7,8)
(1,2),(2,12),(4,10),(9,4),(6,8),(11,5),(7,11),(10,6),(8,7),(5,9),(3,13),(13,14),(14,3),(12,1)

15:161.5
(5,5),(3,2),(14,1),(15,14),(1,15),(2,3),(4,4),(10,11),(6,6),(7,7),(12,13),(9,9),(13,12),(8,8),(11,10)
(13,2),(11,5),(5,10),(10,6),(3,12),(7,9),(8,8),(4,13),(9,7),(6,11),(12,4),(14,3),(15,15),(1,14),(2,1)
(4,13),(7,9),(8,8),(3,12),(9,7),(5,10),(12,4),(13,1),(1,2),(2,15),(15,14),(14,3),(11,5),(6,11),(10,6)

16:188.5
(15,14),(16,2),(3,1),(1,3),(2,16),(14,15),(12,12),(6,7),(11,11),(4,5),(8,8),(9,9),(5,4),(10,10),(7,6),(13,13)

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


14/12/14
26
Using some programs from Markus Sigg's polygon optimization toolbox, I've found an improvement of Tom Rokicki's Max 131:16574
improved to
Max 131:16576
which achieves the optimum area.

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


25/04/17
3
Wow, incredible!

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


14/12/14
26
This was an easy prey:
Tomas Rokicki's Max149:21532.5
improved to the optimal
Max149:21535

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


01/06/12
772
Adelaide, Australia
Great work!

 Профиль  
                  
 
 Re: Al Zimmermann - Polygonal Areas
Сообщение03.05.2017, 17:52 


03/05/17
3
I have done exhaustive searches up to N = 11 for minimum and maximum

The minimum results follow. I have listed the solutions where the #ofconfigs differs from yae9911 list
3 1.5 # 1
4 1.0 # 1
5 1.5 # 2
(1,1), (2,2), (4,5), (3,3), (5,4),
(1,2), (3,3), (4,4), (2,1), (5,5),

6 4.0 # 2
7 4.5 # 3
8 3.5 # 4
9 4.5 # 1

10 4.0 # 3
(1,3), (5,6), (8,8), (6,5), (3,1), (10,7), (4,2), (9,9), (2,4), (7,10),
(1,3), (5,6), (8,8), (3,1), (10,7), (4,2), (6,5), (9,9), (2,4), (7,10),
(1,3), (8,8), (3,1), (10,7), (4,2), (6,5), (9,9), (5,6), (2,4), (7,10),

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

The above results just confirm TomSirgedas minimums
Processing Tom's minimums upto 20 to remove symmetries the #ofconfigs are
12 6.0 # 12
13 6.0 # 6
14 6.5 # 5
15 7.0 # 11
16 7.0 # 4
17 7.5 # 11
18 8.0 # 19
19 8.5 # 17
20 9.0 # 55

The maximum results are
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 # 2
(1,2), (2,7), (4,6), (5,4), (6,3), (3,8), (8,9), (9,5), (7,1),
(1,2), (2,8), (5,4), (4,6), (6,5), (3,7), (8,9), (9,3), (7,1),

10 59.0 # 3
11 75.5 # 5
(1,1), (2,9), (4,8), (8,3), (7,5), (6,6), (9,4), (5,7), (3,10), (10,11), (11,2),
(1,1), (2,9), (5,7), (8,3), (6,6), (7,5), (9,4), (4,8), (3,10), (10,11), (11,2),
(1,2), (2,9), (4,8), (8,3), (7,5), (6,6), (9,4), (5,7), (3,10), (10,11), (11,1),
(1,2), (2,9), (5,7), (6,6), (8,3), (7,5), (9,4), (4,8), (3,11), (11,10), (10,1),
(1,3), (4,4), (8,9), (7,7), (6,6), (9,8), (5,5), (3,2), (10,1), (11,10), (2,11),

I am running 12 for minimums and maximums. I am sure the minimum will just confirm Tom's results
I expect to have results in about three weeks.

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


14/12/14
26
All, I have started to edit drafts of 4 new OEIS sequences to document the results for small n. If you could have a look at the drafts I'd be grateful for suggestions and feedback. Links to examples and some visualizations will be added.

Values of Minimum Area
Number of Configurations with Minimum Area

Values of Maximum Area
Number of Configurations with Maximum Area

If you are a registered OEIS user you can even log in and edit the sequence drafts.

BTW, we have found some further improvements of the Contest and Post Contest results since my last post. The data will be provided later in a separate post.

Hugo Pfoertner

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


14/12/14
26
List of improvements continued:

Min 331: 169.0
Min 257: 131.5
Min 293: 149.5
Min 419: 215.5
Min 191: 96.0
Max 257: 64892.5

Continued in next post.

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


14/12/14
26
Continued list of improvements found by "polygon engineering" using Markus Sigg's Tabu-enhanced breadth first search programs:

Max 467: 215981.0
Max 373: 137451.5
Min 373: 188.0
Max 167: 27140.5
Max 521: 269092.0

One more continuation follows.

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

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



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

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


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

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