Минимальная выпуклая оболочка периметра подмножества точечного множества
Учитывая n точек на плоскости. Нет 3 являются коллинеарными.
Учитывая число k.
Найти подмножество k точек, таких, что выпуклая оболочка k точек имеет минимальный периметр из любой выпуклой оболочки подмножества из k точек.
Я могу думать, что наивный метод работает в O (n ^ k k log k). (Найдите выпуклую оболочку каждого подмножества размера k и выведите минимум).
Я думаю, что это проблема NP, но я не могу найти ничего подходящего для сокращения.
У кого-нибудь есть идеи по этой проблеме?
Пример,
the set of n=4 points {(0,0), (0,1), (1,0), (2,2)} and k=3
Результат:
{(0,0),(0,1),(1,0)}
Так как это множество содержит 3 точки, выпуклая оболочка и периметр результата меньше, чем у любых других множеств из 3 точек.
Ответы
Ответ 1
Это можно сделать в O (kn ^ 3) и O (kn ^ 2) пробел (или, может быть, O (kn ^ 3), если вы хотите фактические точки).
Эта статья: http://www.win.tue.nl/~gwoegi/papers/area-k-gons.pdf
by Eppstein et al., имеет алгоритмы для решения этой проблемы для минимального периметра и других весовых функций, таких как площадь, сумма внутренних углов и т.д., которые следуют определенным ограничениям, хотя название говорит о минимальной площади (см. следствие 5.3 для периметра).
Основная идея - подход к динамическому программированию (см. первые параграфы раздела 4):
Предположим, что S - заданное множество точек, Q - выпуклая оболочка из k точек с минимальным периметром.
Пусть p1 - самая нижняя точка Q, p2 и p3 - следующие точки на корпусе в порядке против часовой стрелки.
Мы можем разложить Q на треугольник p1p2p3 и выпуклую оболочку k-1 точек Q '(которая разделяет сторону p1p3 с треугольником p1p2p3).
Основное замечание состоит в том, что Q 'является оптимальным для k-1, в котором самой нижней точкой является p1, а следующая точка p3, а все точки Q' лежат на одной стороне линии p2- > p3.
Таким образом, поддерживая 4d-массив оптимальных многоугольников для каждой четверки (pi, pj, pk, m) такой, что
- многоугольник является выпуклой оболочкой точно m точек из S.
- pi - самая нижняя точка полигона.
- pj - следующая вершина в порядке против часовой стрелки,
- все точки многоугольника лежат слева от прямой pi → pj.
- все точки лежат на одной стороне pj- > pk при pi.
может помочь найти оптимальные многоугольники при m = k, учитывая оптимальные многоугольники для m <= k-1.
В документе описывается, как это сделать, чтобы достичь заявленного пространства и временных ограничений.
Надеюсь, что это поможет.
Ответ 2
Это не совсем точное решение. На самом деле, это довольно больно для реализации, но это, безусловно, дает многочленную сложность. Хотя сложность также велика (n ^ 5 * k - моя приблизительная оценка), кто-то может найти способ ее улучшить или найти здесь идею для лучшего решения. Или этого может быть достаточно для вас: даже эта сложность намного лучше, чем грубая сила.
Примечание: оптимальное решение (set S
) с корпусом H
включает все точки из orignal, установленные внутри H
. В противном случае мы могли бы выбросить одну из пограничных точек H
и включить эту пропущенную точку, уменьшая периметр.
( обновление, как "оптимизация" mbeckish)
Предположение: две точки из набора не образуют вертикальную линию. Этого можно добиться легко, вращая весь набор точек на некоторый иррациональный угол вокруг начала координат.
Из-за предположения выше, любой сложный корпус имеет одну самую левую и одну самую правую точку. Кроме того, эти две точки делят корпус на части top
и bottom
.
Теперь возьмем один сегмент из части top
этого корпуса и один из части bottom
. Позвольте назвать эти два сегмента middle segments
и периметр правой части этого корпуса - right
.
Примечание: эти два сегмента - это все, что нам нужно знать о правой части нашего выпуклого корпуса, чтобы продолжить строительство слева. Но иметь только два очка вместо 4 недостаточно: мы не могли поддерживать условие "выпуклости" таким образом.
Это приводит к решению. Для каждого набора точек {p0, p1, p2, p3} и числа i
(i <= k) мы сохраняем минимальный периметр right
, который может быть достигнут, если [p0, p1], [p2, p3] два сегмента middle
и i
- это количество точек в части right
этого решения (включая те, что внутри него, а не только на границе).
Мы проходим через все точки справа налево. Для каждой новой точки p
проверяем все комбинации точек {p0, p1, p2, p3}, так что точка p может продолжить эту оболочку влево (либо на top
, либо на части bottom
). Для каждого такого набора и размера i
мы уже сохраняем оптимальный размер периметра (см. Выше).
Примечание: если вы добавите точку p
в right-hull
, образованную точками {p0, p1, p2, p3}, вы увеличите размер набора i
как минимум на 1. Но иногда это число будет > 1: вам нужно будет включить все точки в треугольник {p, p0, p2}. Они не на корпусе, а внутри.
Алгоритм завершен:) Кроме того, несмотря на страшную сложность, вы можете заметить, что не все сегменты [p0, p1], [p2, p3] могут быть middle
сегментами: он должен существенно сократить фактическое время вычисления.
update. Это обеспечивает только оптимальный размер периметра, а не сам набор. Но поиск набора прост: для каждого "состояния" выше вы храните не только размер периметра, но и добавили последнюю точку. Затем вы можете "отследить" свое решение. Это довольно стандартный трюк, я полагаю, это не проблема для вас, вы, кажется, хорошо разбираетесь в алгоритмах:)
update2 Это по существу DP (динамическое программирование), только немного раздутый
Ответ 3
Одна возможная оптимизация: вы можете игнорировать любые подмножества, у которых выпуклая оболочка содержит точки, которые не находятся в подмножестве.
Доказательство:
Если ваша выпуклая оболочка содержит точки, которые не находятся в вашем подмножестве, удалите точку из вашего подмножества, находящегося на корпусе, и замените ее точкой внутри корпуса. Это даст оболочку равного или меньшего периметра.
Ответ 4
В плоском случае вы можете использовать алгоритм, известный как марш Джарвиса, который имеет худшую сложность O (n ^ 2). В этом алгоритме вы начинаете строить корпус в произвольной точке, а затем проверяете, какая точка должна быть добавлена дальше. Псевдокод, взятый из wikipedia:
jarvis(S)
pointOnHull = leftmost point in S
i = 0
repeat
P[i] = pointOnHull
endpoint = S[0] // initial endpoint for a candidate edge on the hull
for j from 1 to |S|-1
if (S[j] is on left of line from P[i] to endpoint)
endpoint = S[j] // found greater left turn, update endpoint
i = i+1
pointOnHull = endpoint
until endpoint == P[0] // wrapped around to first hull point
Насколько я понимаю, выпуклые оболочки уникальны для каждого набора точек, поэтому нет необходимости находить минимум. Вы просто найдете его, и по определению он будет самым маленьким.
Изменить
Опубликованное решение решает для выпуклого корпуса с наименьшим количеством точек. Любой корпус с большим количеством точек будет иметь более длинный периметр, и я неправильно понял вопрос о поиске минимального периметра вместо минимального периметра для набора с точками K.
Эта новая проблема, вероятно, NP, как подозревается, и наиболее похожа на проблему с самым длинным путем. К сожалению, мне не хватает изобретательности, чтобы обеспечить достойное сокращение.