Al Zimmermann - Polygonal Areas

[dimkadimon]

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)

[yae9911]

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.

[dimkadimon]

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.

[TomSirgedas]

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)).

[dimkadimon]

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?

[TomSirgedas]

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.

[dimkadimon]

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)

[yae9911]

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.

[Alex1a]

Wow, incredible!

[yae9911]

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

[dimkadimon]

Great work!

[MichaelC]

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.

[yae9911]

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

[yae9911]

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.

[yae9911]

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.