Вычислительная геометрия

n)
Последовательный (открытый) алгоритм - О(n2)
(в перспективе О(n log n))

Какова

нижняя граница задачи ВО?
Далее лекция 2

число раз превосходят f (n) при достаточно большом n,
используется обозначение

О(f(n)).
Запись g (n) ∈ О(f(n)) означает, что
cуществуют:
вещественная константа C > 0 и
натуральная константа n0 ,
для которых g (n) ≤ C f (n) при всех n ≥ n0

Асимптотические оценки Обозначения О(f(n)), Ω(f(n)), Θ(f(n))

менее чем в постоянное число раз превосходят f (n) при достаточно

большом n, используется обозначение Ω(f(n)).
Запись g (n) ∈ Ω(f(n)) означает, что
существуют :
вещественная константа C > 0 и
натуральная константа n0 ,
для которых g (n) ≥ C f (n) при всех n ≥ n0.

же порядка, что и f (n) при достаточно большом n, используется

обозначение Θ(f(n))
Запись g (n) ∈  Θ(f(n)) означает, что
существуют :
вещественные константы C1 > 0 и C2 > 0 и
натуральная константа n0 , для которых
C1 f (n) ≤ g (n) ≤ C2 f (n) при всех n ≥ n0

и POut(A,B) ∈ O(τ(n)), то говорят, что задача A «τ(n)

– преобразуется» в задачу B.

A → B

POut(A,B)

Алгоритм B

τ(n)

времени) & (A → B)
⇒
(B требует не менее T(n)

– O(τ(n)) времени).

Док-во (от противного):
Пусть B требует менее T(n) – O(τ(n)) времени,
тогда A может быть решена за время
Меньшее, чем T(n) – O(τ(n)) + O(τ(n)) = T(n),
что противоречит посылке

времени) & (A → B)
⇒
(A требует не более T(n)

+ O(τ(n)) времени).
----------------------------------------------------------------
Все это при τ(n) = O(T(n))
-----------------------------------------------------------
О(n) – для верхних оценок,
Ω(n) – для нижних оценок,
Θ(n) – для асимптотически точных оценок

xn). Размер задачи - n.
Задача ВО:
Вход: S = (p1,

p2, …, pn), где pj = (xj, yj).
Размер задачи - n.
Выход:
CH(S) - упорядоченный список вершин ВО

точку.
2) Сортировка по полярному углу – Sort
3) Преобразование выхода

Sort в выход CH(S) – обход Грэхема.

Отсюда – задача ВО м.б. решена
за время O(n log n).
Это верхняя оценка.

xj2).
Точки pj лежат на параболе.
2) Построение CH(S)
3) Найти точку

p* с минимальным значением x (за O(n)).
Пройти по списку и получить упорядоченный набор sort(X) (за O(n)).

Отсюда – задача ВО имеет
нижнюю оценку сложности Ω(n log n).

выпуклых оболочек (1)
Func MergeCH(S): List;
begin
if ⎥S⎢≤ k then Построить CH(S)

прямым методом
else
{1:} Найти S1 и S2 – разбиение S, такое, что ⎥S1⎢≈ ⎥S2⎢;
{2:} P1 := MergeCH(S1); P2 := MergeCH(S2);
{3:}Return CH_Union_ConvP(P1, P2)
fi
end { MergeCH }

оболочка выпуклых многоугольников P1 и P2}
begin
Найти точку p ∈

] P1 [ ; {т.е. точку p – внутреннюю для P1 }
if not (p ∈ ] P2 [ )
then
Найти клин upv {u, v ∈ P2} и освещенную цепь u → v;
Удалить цепь ] u → v [ из P2, т.е. P2 :=P2 \ { ] u → v [ }
fi;
{ P1 и P2 упорядочены относительно точки p}
L := Слияние списков (L(P1), L(P2));
Применить обход Грэхема к L (результат: P);
Return P
end { CH_Union_ConvP }

+ u(n), n>1. При n=1 T(n)=b.
Пусть u(n) =

O(n), т.е. u(n) ≤ a*n.
Докажем, что T(n) = O(n log n),
т.е. T(n) ≤ С1 n log n + C2, где С1 = а+b, C2 = b.
Действительно,
T(n) ≤ 2 (С1 (n/2) log (n/2) + C2) + a*n =
= С1n log n + 2C2 – С1n + a*n = С1n log n + b +(b-bn) ≤
≤ С1 n log n + C2

– разбиение данных на две или более составляющих (части); если

размер данных меньше некоторой пороговой величины, то возвращается готовый результат.
2. Рекурсия – рекурсивно решается каждая из подзадач для составляющих.
3. Слияние – полученные результаты для составляющих объединяются (сливаются) в единый результат.
Быстрая сортировка – тоже пример подхода «разделяй и властвуй». Основные фазы: разделение и рекурсивные вызовы. Фаза слияния тривиальна и не требует дополнительных действий.

u(n);
T(1) = b.
Разделение+Слияние: u(n) ≤ an;
Тогда T(n)

= O(n log2n).

Сложность алгоритма
сбалансированного разделения и слияния

2q (для простоты).
Тогда T(n) = 2T(n/2)

+ an; T(1) = b.
T(n) = 2(2T(n/22) + an/2) + an= 22T(n/22) + 2an=
= 22(2T(n/23) + an/22) + 2an= 23T(n/23) + 3an=
=…= 2kT(n/2k) + kan;
При k=q: T(n/2k) =T(1) = b, 2k = n, q = log2n
T(n) = 2kT(n/2k) + kan = bn + an log2n ≤ Cn log2n ,
где С = a + b (например).
Т.о. T(n) = O(n log2n).

решение
T(n) = T(⎣n/2⎦ ) + T(⎡n/2⎤ ) + u(n);

T(1) = b
при u(n) = O(n) есть T(n) = O(n log2n).

Пусть u(n) ≤ аn и T(k) ≤ Ck log2k при k < n.
T(n) ≤ C ⎣n/2⎦ log2 ⎣n/2⎦ + C ⎡n/2⎤ log2 ⎡n/2⎤ + аn ≤
⎣x⎦ ≤ x, ⎡x⎤ < x + 1
≤ C ⎣n/2⎦ log2(n/2)+ C ⎡n/2⎤ log2 (n/2 +1) + аn ≤

(n/2)(1 + 2/n) + аn ≤
≤ C ⎣n/2⎦ log2(n/2)+ C

⎡n/2⎤ log2 (n/2)+C ⎡n/2⎤ log2(1 + 2/n) + аn ≤
log2 (x +1) ≤ x, ⎣n/2⎦ + ⎡n/2⎤ = n/2
≤ C n log2(n/2)+ C ⎡n/2⎤ (2/n) + аn ≤
≤ C n log2(n/2)+ C (n/2+1) (2/n) + аn ≤
≤ C n log2n + C (1 + 2/n) + (а – С)n ≤ C n log2n (при C > a)