Интернет магазин китайских планшетных компьютеров

Компьютеры - Алгоритм Киркпатрика

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

1. Если |S| k₀, то построить выпуклую оболочку одним из известных методов и остановиться, иначе перейти к шагу 2.
2. Разобьем исходное множество S произвольным образом на два примерно равных по мощности подмножества S₁ и S₂.
3. Рекурсивно находим выпуклые оболочки каждого из подмножеств S₁ и S₂.
4. Строим выпуклую оболочку исходного множества как выпуклую оболочку объединения двух выпуклых многоугольников CH и CH.

Поскольку: CH = CH = CH CH), сложность этого алгоритма является решением рекурсивного соотношения T 2T + f, где f — время построения выпуклой оболочки объединения двух выпуклых многоугольников, каждый из которых имеет около N/2 вершин. Далее будет показано, что T = O.

Определения

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