WikiSort.ru - Не сортированное

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

Описание

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

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

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

Определения

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

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

Реализация

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

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

Теперь получена выпуклая оболочка объединения выпуклых многоугольников ${\displaystyle P_{1}\cup P_{2}}$ .

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

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

Ссылки

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

Для улучшения этой статьи желательно: Проверить достоверность указанной в статье информации. Викифицировать статью.