Алгоритм Киркпатрика

Построение выпуклой оболочки методом «разделяй и властвуй» — алгоритм построения выпуклой оболочки.

Описание

Дано множество <math> S </math>, состоящее из <math> N </math> точек.

1. Если <math> N \leq N_0</math> (<math>N_0</math> — некоторое небольшое целое число), то построить выпуклую оболочку одним из известных методов и остановиться, иначе перейти к шагу 2.
2. Разобьем исходное множество <math> S </math> произвольным образом на два примерно равных по мощности подмножества <math>S_1</math> и <math>S_2</math> (пусть <math>S_1</math> содержит <math> N/2 </math> точек, а <math>S_2</math> содержит <math> N - N/2 </math> точек).
3. Рекурсивно находим выпуклые оболочки каждого из подмножеств <math>S_1</math> и <math>S_2</math>.
4. Строим выпуклую оболочку исходного множества как выпуклую оболочку объединения двух выпуклых многоугольников <math> CH(S_1) </math> и <math> CH(S_2) </math>.

Поскольку: <math> CH(S) = CH(S1 \cup S2) = CH(CH(S_1) \cup CH(S_2)) </math>, сложность этого алгоритма является решением рекурсивного соотношения <math> T(N) \leq 2 T(N/2) + f(N)</math> , где <math> f(N) </math> — время построения выпуклой оболочки объединения двух выпуклых многоугольников, каждый из которых имеет около <math> N/2 </math> вершин. Далее будет показано, что <math> T(N) = O(N \log N) </math>.

Определения

Опорной прямой к выпуклому многоугольнику <math> P </math> называется прямая <math> l </math>, проходящая через некоторую вершину многоугольника <math> P </math> таким образом, что все внутренние точки многоугольника лежат по одну сторону от прямой <math> l </math>.

К выпуклому многоугольнику <math> P </math> можно построить опорные прямые из точки <math> A </math>, не принадлежащей ему. Воспользуемся тем, что прямая <math> AP_i</math>, где <math>P_i</math> — некоторая вершина многоугольника <math> P </math>, является опорной к <math> P </math> в том и только в том случае, если ребра <math> (P_{i-1}, P_i) </math> и <math> (P_i, P_{i+1}) </math> лежат в одной полуплоскости, ограниченной этой прямой. Нетрудно видеть, что для построения опорных прямых требуется в худшем случае один обход вершин многоугольника <math> P </math>, то есть они ищутся за линейное время.

Реализация

Пусть мы уже имеем построенные выпуклые оболочки <math> P_1 </math> и <math> P_2 </math>.

1. Найдём некоторую внутреннюю точку <math> A </math> многоугольника <math> P_1 </math> (например, центроид любых трёх вершин <math> P_1 </math>). Такая точка <math> A </math> будет внутренней точкой <math> CH(P_1 \cup P_2) </math>.
2. Возможно два случая:
   1. Точка <math> A </math> не является внутренней точкой многоугольника <math> P_2 </math>. Проводим две опорные прямые для многоугольника <math> P_2 </math>, проходящие через точку <math> A </math>. Эти опорные прямые проходят через вершины <math> B </math> и <math> C </math> многоугольника <math> P_2 </math>. Все точки внутри треугольника <math> ABC </math> не принадлежат границе выпуклой оболочки <math> CH(P1 \cup P2) </math>. Все остальные точки упорядочиваем по полярному углу относительно точки <math> A </math>, слиянием двух упорядоченных списков вершин за время <math> O(N_1) + O(N_2) = O(N) </math>, а затем применяем к полученному списку метод обхода Грэхема, требующий лишь линейное время.
   2. Точка <math> A </math> является внутренней точкой многоугольника <math> P_2 </math>. Упорядочиваем вершины обоих многоугольников относительно центра <math> A </math>, сливая два упорядоченных списка вершин <math> P1 </math> и <math> P_2 </math> за <math> O(N) </math>.
3. Теперь к полученному списку вершин можно применить алгоритм Грэхема за исключением фазы сортировки точек по полярной координате, тогда он будет выполнен за линейное время.

Теперь получена выпуклая оболочка объединения выпуклых многоугольников <math> P_1 \cup P_2 </math>.

Сложность алгоритма

В сумме все три фазы алгоритма выполняются за время <math> O(N) </math>. Таким образом, <math> f(N) = O(N) </math> и получаем соотношение <math> T(N) \leq 2 T(N/2) + O(N) </math>, решением которого, как известно, является <math> T(N) = O(N \log N) </math>, что и определяет сложность алгоритма.

Ссылки

• [www.cs.umd.edu/~samir/754/kshand.ps www.cs.umd.edu/~samir/754/kshand.ps] (англ.)

Отрывок, характеризующий Алгоритм Киркпатрика

– Еще успеем, ваше превосходительство, – сквозь зевоту проговорил Кутузов. – Успеем! – повторил он.
В это время позади Кутузова послышались вдали звуки здоровающихся полков, и голоса эти стали быстро приближаться по всему протяжению растянувшейся линии наступавших русских колонн. Видно было, что тот, с кем здоровались, ехал скоро. Когда закричали солдаты того полка, перед которым стоял Кутузов, он отъехал несколько в сторону и сморщившись оглянулся. По дороге из Працена скакал как бы эскадрон разноцветных всадников. Два из них крупным галопом скакали рядом впереди остальных. Один был в черном мундире с белым султаном на рыжей энглизированной лошади, другой в белом мундире на вороной лошади. Это были два императора со свитой. Кутузов, с аффектацией служаки, находящегося во фронте, скомандовал «смирно» стоявшим войскам и, салютуя, подъехал к императору. Вся его фигура и манера вдруг изменились. Он принял вид подначальственного, нерассуждающего человека. Он с аффектацией почтительности, которая, очевидно, неприятно поразила императора Александра, подъехал и салютовал ему.
Неприятное впечатление, только как остатки тумана на ясном небе, пробежало по молодому и счастливому лицу императора и исчезло. Он был, после нездоровья, несколько худее в этот день, чем на ольмюцком поле, где его в первый раз за границей видел Болконский; но то же обворожительное соединение величавости и кротости было в его прекрасных, серых глазах, и на тонких губах та же возможность разнообразных выражений и преобладающее выражение благодушной, невинной молодости.
На ольмюцком смотру он был величавее, здесь он был веселее и энергичнее. Он несколько разрумянился, прогалопировав эти три версты, и, остановив лошадь, отдохновенно вздохнул и оглянулся на такие же молодые, такие же оживленные, как и его, лица своей свиты. Чарторижский и Новосильцев, и князь Болконский, и Строганов, и другие, все богато одетые, веселые, молодые люди, на прекрасных, выхоленных, свежих, только что слегка вспотевших лошадях, переговариваясь и улыбаясь, остановились позади государя. Император Франц, румяный длиннолицый молодой человек, чрезвычайно прямо сидел на красивом вороном жеребце и озабоченно и неторопливо оглядывался вокруг себя. Он подозвал одного из своих белых адъютантов и спросил что то. «Верно, в котором часу они выехали», подумал князь Андрей, наблюдая своего старого знакомого, с улыбкой, которую он не мог удержать, вспоминая свою аудиенцию. В свите императоров были отобранные молодцы ординарцы, русские и австрийские, гвардейских и армейских полков. Между ними велись берейторами в расшитых попонах красивые запасные царские лошади.
Как будто через растворенное окно вдруг пахнуло свежим полевым воздухом в душную комнату, так пахнуло на невеселый Кутузовский штаб молодостью, энергией и уверенностью в успехе от этой прискакавшей блестящей молодежи.
– Что ж вы не начинаете, Михаил Ларионович? – поспешно обратился император Александр к Кутузову, в то же время учтиво взглянув на императора Франца.
– Я поджидаю, ваше величество, – отвечал Кутузов, почтительно наклоняясь вперед.
Император пригнул ухо, слегка нахмурясь и показывая, что он не расслышал.
– Поджидаю, ваше величество, – повторил Кутузов (князь Андрей заметил, что у Кутузова неестественно дрогнула верхняя губа, в то время как он говорил это поджидаю ). – Не все колонны еще собрались, ваше величество.
Государь расслышал, но ответ этот, видимо, не понравился ему; он пожал сутуловатыми плечами, взглянул на Новосильцева, стоявшего подле, как будто взглядом этим жалуясь на Кутузова.