Al Zimmermann - Polygonal Areas

[Vovka17]

dmd в сообщении #1179152 писал(а):

максимальная "рамка" из 5-ти точек больше максимальной "рамки" из 6-ти точек на 3/2 для любого n.

Вот и я когда-то начинал было строить рамки, но, как оказалось, часто в решениях, из "плохой" рамки возможно сделать очень тонкую вырезку и эта "плохая" рамка оказывается уже предпочтительнее "хорошей" из которой вырезка большая.

[Archimedes]

"Кривые штаны" тоже уже получил.
Спасибо за симметричные примеры минимумов, по-моему этот метод может очень сильно помочь для больших n.

Сразу применил подходы по оптимизации из прошлых задач: запоминание частичных сумм площадей, исключение ненужных проверок на наклон и пересечение, пропуск просчёта заведомо неприемлемых точек.
Всё равно, перебором можно найти только 11х11.
Даже 17х17 перебрать нереально. (Может быть симметричный минимум получится).

Испытываю проблемы нахождения опорного (любого) решения для n>257. Меньшие уже нашёл, зарядил 3 4-хпоточных процессора перебирать варианты. Пока выше 31-го места не поднимался.

[dmd]

Решение для N10 получилось преобразовать в решение для N11, не оптимальное конечно, но с сохранением симметрии точек.

[dimkadimon]

Vovka17 в сообщении #1179133 писал(а):

Вроде это максимумы для n=8, 9, 10. Гарантии на них не распространяются?

Я получил те же самые результаты, поэтому вероятно они оптимальные.

-- 23.12.2016, 17:48 --

Archimedes в сообщении #1179375 писал(а):

Испытываю проблемы нахождения опорного (любого) решения для n>257

Для этого у меня сработал вот такой метод. Начинаем с случайных двух точек. Добавляем первую точку которая создает легальный полигон. Повторяем пока не добавим все $n$ точек. Точки можно вставлять в любое ребро готового полигона. Есть хорошая вариация. Вместо "первой" точки находим ту точку которая дает наибольшую/наименьшую площадь. Если слишком медленно то можно не все варианты перебирать, а только часть, например $1/10$.

[Herbert Kociemba]

My program can brute force up to N=11 without problem. So indeed the results up to N=11 are optimal. In the moment I brute force N=12 just for fun because I still do not have the idea for a good approach for N=29 and larger.

[dimkadimon]

dmd в сообщении #1179401 писал(а):

запоминание частичных сумм площадей, исключение ненужных проверок на наклон и пересечение, пропуск просчёта заведомо неприемлемых точек.

Очень интересно. Спасибо за подсказки. Теперь надо подумать как вы это сделали.

[erraen]

Archimedes в сообщении #1179375 писал(а):

Испытываю проблемы нахождения опорного (любого) решения для n>257.

Существуют относительно простые решения с регулярной структурой (достаточно выч. мощности программируемого калькулятора) как для минимума, так и для максимума, дающие относительно неплохой результат.

[Archimedes]

erraen в сообщении #1179419 писал(а):

Существуют относительно простые решения с регулярной структурой (достаточно выч. мощности программируемого калькулятора) как для минимума, так и для максимума, дающие относительно неплохой результат.

Огромное спасибо! Нарисовал алгоритм.

[Archimedes]

Кстати, на первых порах на регулярных многоугольниках можно хорошо продвинуться. :)
Сначала нарисовал алгоритм "Ёлочка": ...(5,n-1)(4,4),(2,n),(1,1),(n,2),(3,3),(n-1,5)...
Результат близок к n*n/2, поэтому ни к минимуму, ни к максимуму он не близок.
Потом нарисовался алгоритм "Пила" в двух модификациях. На больших n это дало больше чем случайно просчитанные многоугольники. :)
Кроме того, обнаружил ошибку в своём алгоритме просчёта пересечений. Вроде исправил.

[jcmeyrignac]

Found this sequence:
http://oeis.org/A140466/b140466.txt

[dimkadimon]

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

Found this sequence:
http://oeis.org/A140466/b140466.txt

Looks like there are plenty of slopes to go around. Even for $n=17$ we have $C^{384}_{17} = 1.6*10^{29}$, which is actually larger than the total number of point placements: $(17!)^2=1.2*10^{29}$.

You are not competing JC?

-- 27.12.2016, 13:51 --

Кто нибудь пробовал генерировать симметричные решения? На вид у многих хороших решений есть симметрия, но воспроизвести эту симметрию автоматически оказалось не так просто. Если приглядеться то симметрия не совсем идеальная и именно это сложно оптимизировать. У меня симметричные решения больше $n=29$ не получаются.

-- 27.12.2016, 14:01 --

Для максимальных решений сколько лучше иметь "входов" внутрь? Можно ли всегда обойтись одним входом?

[dmd]

Вручную построил симметричное решение для N11, и на компе для N17 и N23. Симметричное в точках, линии одна-три ложатся без симметрии.

[dimkadimon]

Минимальная площадь для выпуклых полигонов с целыми координатами: https://oeis.org/A070911

[dimkadimon]

Вот полезная под-задача. Даются точки в плоскости. Надо найти полигон минимальной площади который проходит через все точки. Оказывается задача NP-Hard:
http://mathoverflow.net/questions/19211 ... h-contains

Тут приведен приблизительный алгоритм нахождения такого полигона:
http://oa.upm.es/19287/1/INVE_MEM_2011_121744.pdf

[Archimedes]

Мой рейтинг достиг 23.
До этого придумал несколько алгоритмов, которые ускоряли приближение к заветным 25. :)
Сейчас продвижение идёт со скоростью около 0.05 в сутки. А значит нужны новые идеи.

Где-то тут раньше обсуждали что максимум - это тот же минимум, только с инверсией. Идея богатая :), но пока проверил её только на 12min -> 17max и 11min -> 17max. Ничего даже близкого к максимуму не получается: проигрыш найденному другими алгоритмами около 5 ед. Возможно этот подход даст больше на больших N.