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

Question

Дано n точек на плоскости. № 3 коллинеарны.

Дано число к.

Найдите подмножество из 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 точек.

Answer 1

Это можно сделать за время O (kn ^ 3) и пространство O (kn ^ 2) (или, возможно, O (kn ^ 3), если вы хотите фактические точки).

Эта статья: *Eppstein et al., 1003 *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, в которомсамая нижняя точка р1 и йСледующая точка - это p3, и все точки Q 'лежат на одной стороне линии p2-> p3.

Таким образом, поддерживается 4d массив оптимальных многоугольников для каждой четверки (pi, pj, pk,m) такой, что

• многоугольник представляет собой выпуклую оболочку с точно m точками S.
• pi является самой нижней точкой многоугольника.
• pj являетсяследующая вершина в порядке против часовой стрелки,
• все точки многоугольника лежат слева от линии pi -> pj.
• все точки лежат на одной стороне от pj-> pkкак это делает пи.

может помочь нам найти оптимальные полигоны для m = k, учитывая оптимальные полигоны для m <= k-1. </p>

В статье описывается, как именноо том, чтобы сделать это, чтобы достичь заявленных границ пространства и времени.

Надеюсь, это поможет.

Answer 2

Это не совсем симпатичное решение. На самом деле, это довольно сложно реализовать, но это, безусловно, дает полиномиальную сложность. Хотя сложность также велика (n ^ 5 * k - моя грубая оценка), кто-то может найти способ улучшить ее или найти здесь идею для лучшего решения. Или вам этого может быть достаточно: даже эта сложность намного лучше, чем грубая сила.

Примечание : оптимальное решение (установлено S) с оболочкой H включает все точки из оригинального набора внутри H. В противном случае мы могли бы отбросить одну из граничных точек H и включить эту пропущенную точку, уменьшив периметр.
( обновление точно так же, как 'оптимизация' mbeckish опубликовано)

Предположение : никакие две точки из множества не образуют вертикальную линию. Это может быть легко достигнуто вращением всего набора точек на некоторый иррациональный угол вокруг начала координат.

Из-за предположения, приведенного выше, любой сложный корпус имеет одну крайнюю левую и одну крайнюю правую точки. Кроме того, эти две точки делят корпус на top и bottom части.

Теперь давайте возьмем один сегмент из top части этого корпуса и один из bottom. Давайте назовем эти два сегмента middle segments и периметр правой части этого корпуса - right периметр.
Примечание : эти два сегмента - это все, что нам нужно знать о правой части нашего выпуклого корпуса, чтобы продолжить строить его слева. Но иметь только две точки вместо 4 недостаточно: мы не можем поддерживать условие «выпуклости» таким образом.

Это приводит к решению . Для каждого набора точек {p0, p1, p2, p3} и числа i (i <= k) мы храним минимальный периметр <code>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 (динамическое программирование), только немного раздутый

Answer 3

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

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

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

Answer 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-точками.больше всего похоже на проблему самого длинного пути.К сожалению, мне не хватает изобретательности, чтобы обеспечить достойное сокращение.