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

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

ОписаниеПравить

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

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

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

ОпределенияПравить

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

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

РеализацияПравить

Пусть мы уже имеем построенные выпуклые оболочки $P_1$$P_{1}$  и $P_2$$P_{2}$ .

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

Теперь получена выпуклая оболочка объединения выпуклых многоугольников $P_1\cup <!--\; \cup \; -->P_2$$P_{1}\cup P_{2}$ .

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

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

СсылкиПравить

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