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



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

23 января 2011


Оглавление:
1. Алгоритм Киркпатрика
2. Реализация
3. Сложность алгоритма



Описание

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

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

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

Определения

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



Просмотров: 1558


<<< Алгоритм Джарвиса
Алгоритм Коэна Сазерленда >>>