Центральный Дом Знаний - Алгоритм Чана

Информационный центр "Центральный Дом Знаний"

Заказать учебную работу! Жми!



ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

      cendomzn@yandex.ru  

Наш опрос

Я учусь (закончил(-а) в
Всего ответов: 2688

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Форма входа

Логин:
Пароль:

Алгоритм Чана

Алгоритм Чана (Тимоти М. Чан, 1996), алгоритм построения выпуклой оболочки конечного множества точек на плоскости. Является комбинацией двух более медленных алгоритмов (сканирование по Грэхему O(nlogn) и заворачивание по Джарвису O(nh)). Недостатком сканирования по Грэхему является необходимость сортировки всех точек по полярному углу, что занимает достаточно много времени O(nlogn). Заворачивание по Джарвису требует перебора всех точек для каждой из h точек выпуклой оболочки, что в худшем случае занимает O(n2).

Алгоритм Чана построения выпуклой оболочки. Трудоёмкость O(nlog h), h — количество точек в выпуклой оболочке. 

Идея А.Ч. заключается в изначальном делении всех точек на группы по m штук в каждой. Соответственно, количество групп равно r = \left \lceil n/m \right \rceil. Для каждой из групп строится выпуклая оболочка сканированием по Грэхему за O(mlog m), то есть для всех групп понадобитсяO(rmlog m) = O(nlog m) времени.

Затем, начиная с самой левой нижней точки, для получившихся в результате разбиения оболочек строится общая выпуклая оболочка по Джарвису. При этом следующая подходящая для выпуклой оболочки точка находится за O(rlog m), так как для того, чтобы найти точку с максимальным тангенсом по отношению к рассматриваемой точке в m-угольнике достаточно затратить O(log m) (точки в m-угольнике были отсортированы по полярному углу во время выполнения алгоритма сканирования Грэхема). В итоге, на обход требуется O(h r \log m) = O\left(\left(hn/m\right)\log m\right) времени.

То есть А.Ч. работает за O\left(\left(n + hn/m\right)\log m\right), при этом, если получить m = h, то за O(nlogh).

Hull(P, m)

1)взять r = \left \lceil n/m \right \rceil. Разделить P на r дизъюнктных подмножеств P_1,\;P_2,\;\ldots,\;P_r мощности не более m;

2)for i = 1 to r do:

(a) вычислить выпуклую оболочку Graham(Pi), сохранить вершины в отсортированном по полярному углу массиве;

3)в качестве p1 взять самую левую и нижнюю точку из P;

4)for k = 1 to m do

(a) for i = 1 to r do

найти и запомнить точку qi из Pi с максимальным углом pk − 1pkqi;

(b) взять в качестве pk + 1 точку q из {q_1,\;q_2,\;\ldots,\;q_r} с максимальным углом pk − 1pkq;

(c) if pk + 1 = p1 return {p_1,\;\ldots,\;p_k};

5) return m маленькое, попробуйте еще;

Ясно, что обход по Джарвису, а следовательно и весь алгоритм, будет корректно работать только если m \geqslant h, но как заранее узнать сколько точек будет в выпуклой оболочке? Надо запускать алгоритм несколько раз, подбирая m и, если m < h, то алгоритм будет возвращать ошибку. Если делать подбор бинарным поиском по n, то в итоге получится время O((nlog h)log n) =O(nlog n), что достаточно долго.

Процесс можно ускорить, если начать с маленького значения и после значительно его увеличивать, пока не получится m \geqslant h. Например, взять 2^{2^t}. При этом t-я итерация займет O(n \log 2^{2^t}) = O(n 2^t). Процесс поиска завершится, когда 2^{2^t} \geqslant h, то есть t = \lceil \mathrm{lg}\, \mathrm{lg}\, h \rceil (lg — двоичный логарифм).

В итоге \sum_{t=1}^{\mathrm{lg}\, \mathrm{lg}\, h} n 2^t = n \sum_{t=1}^{\mathrm{lg}\, \mathrm{lg}\, h} 2^t \leqslant n 2^{1 + \mathrm{lg}\, \mathrm{lg}\, h} = 2 n \,\mathrm{lg}\, h = O(n \log h).

ChanHull(P)

for t = 1 to n do:

(a) взять m = \min(2^{2^t},\; n);

(b) L = Hull(P, m);

(c) if L != «m маленькое, попробуйте еще» return L;

Лит.: David M. Mount Computational Geometry — University of Maryland, 2002. — С. 122.

Loading

Календарь

«  Март 2024  »
ПнВтСрЧтПтСбВс
    123
45678910
11121314151617
18192021222324
25262728293031

Архив записей

Друзья сайта

  • Заказать курсовую работу!
  • Выполнение любых чертежей
  • Новый фриланс 24