Данный n указывает на плоскости. № 3 коллинеарен.
Учитывая номер k.
Найдите подмножество точек k, таких, что выпуклая оболочка точек k имеет минимальный периметр из любой выпуклой оболочки подмножества точек k.
Я могу думать о наивном методе выполнения в O (n^k k, регистрируют 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 точек.
Это можно сделать за время O (kn ^ 3) и пространство O (kn ^ 2) (или, возможно, за O (kn ^ 3), если вам нужны фактические очки).
Эта статья: http://www.win.tue.nl/~gwoegi/papers/area-k-gons.pdf
Эппштейна и др. Содержит алгоритмы решения этой проблемы для минимального периметра. и другие весовые функции, такие как площадь, сумма внутренних углов и т. д., которые подчиняются определенным ограничениям, даже если в заголовке указано минимальное значение площади (периметр см. в следствии 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 = k, учитывая оптимальные многоугольники для m <= k-1.
В документе точно описано, как это сделать, чтобы достичь указанных временных и пространственных ограничений.
Надеюсь, что это поможет.
Одна возможная оптимизация: вы можете игнорировать любые подмножества, выпуклая оболочка которых содержит точки, которых нет в подмножестве.
Доказательство:
Если ваша выпуклая оболочка содержит точки, которых нет в вашем подмножестве, тогда удалите точку из вашего подмножества, которая находится на оболочке, и замените ее точкой внутри оболочки. В результате получится корпус равного или меньшего периметра.
В плоском случае вы можете использовать алгоритм, известный как марш Джарвиса, который имеет сложность наихудшего случая O (n ^ 2). В этом алгоритме вы начинаете строить корпус в произвольной точке, а затем проверяете, какая точка должна быть добавлена следующей. Псевдокод взят из википедии :
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, как предполагалось, и больше всего похожа на проблему самого длинного пути. К сожалению, мне не хватает изобретательности, чтобы обеспечить достойное сокращение.
Это не совсем красивое решение. На самом деле, это довольно сложно реализовать, но это определенно дает полиномиальную сложность. Хотя сложность также велика (n ^ 5 * k - моя приблизительная оценка), кто-то может найти способ ее улучшить или найти здесь идею лучшего решения. Или вам может хватить: даже эта сложность намного лучше, чем брутфорс.
Примечание : оптимальное решение (набор S
) с корпусом H
включает все точки из исходного набора внутри H
.В противном случае мы могли бы отбросить одну из граничных точек H
и включить эту пропущенную точку, уменьшив периметр.
( обновление , как и «оптимизация» mbeckish )
Предположение : никакие две точки из набора не образуют вертикальную линию. Этого легко добиться, повернув всю совокупность точек на некоторый иррациональный угол вокруг начала координат.
В силу сделанного выше предположения любая сложная оболочка имеет одну крайнюю левую и одну крайнюю правую точки. Кроме того, эти две точки делят корпус на верхнюю
и нижнюю
части.
Теперь возьмем один сегмент из верхней
части корпуса и один из нижней
части. Назовем эти два сегмента средними сегментами
и периметр правой части корпуса - правым
периметром.
Примечание : эти два сегмента - это все, что нам нужно знать о правой части нашей выпуклой оболочки, чтобы продолжить ее построение слева. Но двух точек вместо 4 недостаточно: мы не могли бы таким образом обеспечить условие «выпуклости».
Это приводит к решению . Для каждого набора точек {p0, p1, p2, p3} и числа i
(i <= k) мы сохраняем минимальный правый
периметр, который может быть достигнут, если [p0, p1] , [p2, p3] - два средних
сегмента, а i
- количество точек в правой
части этого решения (включая те, что внутри него, не только на границе).
Проходим все точки справа налево.Для каждой новой точки p
мы проверяем все комбинации точек {p0, p1, p2, p3}, так что точка p может продолжать эту оболочку влево (либо на вершине
, либо на нижняя часть
). Для каждого такого набора и размера i
мы уже сохраняем оптимальный размер периметра (см. Параграф выше).
Примечание : если вы добавите точку p
в правую оболочку
, образованную точками {p0, p1, p2, p3}, вы увеличите размер набора i
как минимум на 1. Но иногда это число будет> 1: вам придется включить все точки в треугольник {p, p0, p2}. Их нет на корпусе, а внутри него.
Алгоритм окончен :) Кроме того, несмотря на пугающую сложность, вы можете заметить, что не все сегменты [p0, p1], [p2, p3] могут быть средними
сегментами: это должно сократить фактическое время вычислений существенно.
update Это обеспечивает только оптимальный размер периметра, но не сам набор. Но найти набор просто: для каждого «состояния» выше вы сохраняете не только размер периметра, но и последнюю добавленную точку. Затем вы можете «отследить» свое решение. Это вполне стандартный прием, полагаю, для вас это не проблема, вы, кажется, хорошо разбираетесь в алгоритмах :)
update2 Это по сути DP (динамическое программирование), только немного раздутое