Генерация простых многоугольников

[vmyrik]

Пускай задано фиксированное множество S из N точек на плоскости. Необходимо разработать алгоритм генерации простых многоугольников, вершинами которых есть все точки заданной плоскости S и определить многоугольник минимальной площади.

Перебрать все перестановки точек из S. Каждая перестановка порождает многоугольник. Если в мног-ке есть самопересечения, его отбрасываем, если нет, считаем его площадь и отбираем нужный.

[vmyrik]

Перебрать все перестановки точек из S. Каждая перестановка порождает многоугольник. Если в мног-ке есть самопересечения, его отбрасываем, если нет, считаем его площадь и отбираем нужный.

Слишком большая сложность. Может есть что-нибудь оптимальнее?

Как вариант: Для этого множества построить выпуклую оболочку, а потом в цикле для оставшихся точек и ребер оболочки искать треугольник максимальной площади, который можно отрезать, и таких треугольников мы выбросим столько, сколько точек было внутри оболочки.
Сложность порядка O(N^4)
Но вопросом остается то, получим ли мы в итоге именно минимальную возможную площадь(хотя по логике - да, ведь на каждом шаге отрезаем максимум)

Ваше решение не достигает результата. Представьте себе тонкую спираль на пару-тройку витков. Она и есть оптимум, т.к. ее площадь можно как угодно уменьшать. А Ваш greedy алгоритм ее пропустит.
А вот перебор перестановок, с отсечением всех подмножеств сразу после появления пересечения, хотя бы гарантирует полный ответ. При правильной организации перебора не будет лишних\повторных вычислений.

Да, насчет сложности. Сложность определяется количеством многугольников. Мне кажется, это экспонента, поэтому задача NP-hard.
А хорошо оценить число многоугольников так сразу не берусь.

[vmyrik]

Ваше решение не достигает результата. Представьте себе тонкую спираль на пару-тройку витков. Она и есть оптимум, т.к. ее площадь можно как угодно уменьшать. А Ваш greedy алгоритм ее пропустит.
А вот перебор перестановок, с отсечением всех подмножеств сразу после появления пересечения, хотя бы гарантирует полный ответ. При правильной организации перебора не будет лишних\повторных вычислений.

То есть вы хотите сказать, что площадь спирали равна 0? А края, вроде как, не замкнуты? Похоже на вырожденный случай.

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

[vmyrik]

Вы не могли бы показать на рисунке, а то сложно так сразу представить, как уменьшить ее площадь, чтоб она осталась многоугольником

Нарисуйте сами ломаную закрученную в спираль. А теперь отступите от
всех ее вершин по биссектрисе угла между соседними ребрами на EPS и замкните многоугольник в первой и последней точке таким же коротким ребром. Площадь такого многоугольника будет (почти) L*Eps, где L - длина ломаной. Поскольку Eps можно сделать как угодно малым, то и площадь можно сделать как угодно малой.
Внимание вопрос! Ваш алгоритм умеет строить такие многоугольники?

[vmyrik]

Жаль, но нет, не умеет. Видимо, придется остановиться на методе перебора. Хотя он, даже с улучшениями, за приемлемое время обрабатывает 10-12 точек.