Минимальная выпуклая оболочка периметра подмножества точки установлена

Одна возможная оптимизация: вы можете игнорировать любые подмножества, выпуклая оболочка которых содержит точки, которых нет в подмножестве.

Доказательство:

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

В плоском случае вы можете использовать алгоритм, известный как марш Джарвиса, который имеет сложность наихудшего случая 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 (динамическое программирование), только немного раздутое