Сравнительный анализ алгоритмов построения выпуклой оболочки на плоскости

Категория реферата: Рефераты по математике
Теги реферата: реферат мыло, кредит реферат
Добавил(а) на сайт: Nedel'skij.

В данном алгоритме, в отличие от предыдущего, множество S разбивается на два равномощных подмножества S’ и S’’, а затем рекурсивно строятся отдельно оболочки для каждого из них и объединяются.

CH(S) = CH(S’ ( S’’) = CH(CH(S’) ( CH (S’’))

Сложность этого метода состоит в эффективном нахождении слияния двух выпуклых оболочек. Следующий алгоритм слияния был предложен Шеймосом[vii]:
Пусть у нас есть выпуклые многоугольники P’ и P’’. Нам требуется найти P
– их слияние. Этого берется любая внутренняя точка p для P’ и проверяется на принадлежность P’’. Если она принадлежит, то по теореме 4 мы имеем два упорядоченных относительно полярного угла к p множества. За время равное сумме точек в них мы можем из них получить один упорядоченный список. После чего, используя обход Грэхема за такое же время получить требуемый выпуклый многоугольник.

[pic]

Рис. 2: Так как точка p внутри обоих многоугольников, то вершины, как одного, так и второго, упорядочены относительно полярного угла к p.

В случае, когда p не принадлежит P’’, придется найти левую и правую опорные прямые из p к P’’, pl и pr соответственно. Опорной прямой к выпуклому многоугольнику P будем называть прямую l, проходящую через некоторую вершину этого многоугольника, таким образом, что внутренность P находится по одну сторону от l. Для этого нам достаточно время O(N). Все вершины P’’ между l и r, при движении от l к r против часовой стрелки, убираем из рассмотрения и выполняем те действия, которые выполняли в случае принадлежности.

[pic]

Рис. 3: Так как точка p внутри одного многоугольника, то удаляем все видимые из p вершины второго многоугольника.

Как видно, и в этом случае на слияние требуется время O(N), где N – это общее количество точек в многоугольниках. Отсюда следует теорема:

Теорема 6. Выпуклая оболочка объединения двух выпуклых многоугольников может быть найдена за время, пропорциональное суммарному числу их вершин.

Динамические алгоритмы построения выпуклой оболочки

Все приведенные алгоритмы не являются открытыми, так как требуют изначально знать все точки множества S. Но в некоторых случаях требуется иметь алгоритм способный при поступлении новой точки изменять выпуклую оболочку. В данном случае мы имеем дело с задачей ВО2.
Очевидно, что решение задачи существует. Можно каждый раз после поступления точки использовать обход Грэхема и получить алгоритм со сложностью O(N2 log N), но хотелось бы не приносить в жертву оценку O(N log
N).
Для этого следует обратить внимание на то, что каждую новую точку алгоритм должен или отбрасывать, или вставлять его в список точек образующих выпуклую оболочку. Чтобы получить это оценку, мы на каждую точку должны тратить время O(log N), то есть мы должна находить место вставки и вставлять точку за O(log N). Такой алгоритм построил Препарата[viii].
В этом алгоритме необходимо быстро находить опорные прямые к выпуклому многоугольнику P и проходящие через некоторую точку p. После этого одну из цепей, на которые разбивают опорные точки границу выпуклого многоугольника, заменить на p.
Будем называть опорную прямую pl левой, если многоугольник P лежит справа от pl, и соответственно прямую pr правой, если слева. Точки l и r будем называть опорными. Так же будем различать вогнутые вершины, т.е. те для которых отрезок, соединяющий их и p, пересекает внутренность многоугольника. А те, которые ни вогнутые и ни опорные будут выпуклыми.
При поверке какой-то вершины на вогнутость или выгнутость мы можем определить, где искать опорную точку. Тык же мы должны иметь возможность быстро удалить цепочку вершин и вставить место нее p. Для этого нам нужно хранить многоугольник не писком, как это делалось в предыдущих алгоритмах, а AWL или другим сбалансированным деревом.
В этом дереве T переход к левому потомку будет соответствовать движению по часовой стрелке по выпуклой оболочке, а для правого против часовой стрелки. Для каждого узла в этом дереве мы должны иметь возможность получать доступ к самой левому узлу. Если рассмотреть корневой узел дерева
M и m – самый левый узел, то они разбивают границу выпуклого многоугольника на две цепи, причем одна хранится в левом поддереве M, а вторая в правом. В зависимости от типа вершины М и m, а также от того, какой угол (mpM) – левый или правый, можно определить в каком поддереве находится опорная вершина.
Рассмотрим поиск левой опорной вершины. Если (mpM) – левый а m – вогнутая или то (mpM) – правый а M – выпуклая, то поиск нежно продолжать в левом поддереве, иначе – в правом. Аналогично и для правой опорной вершины.
[pic][pic]

Рис. 4: Два варианта для m, M и p.

Таким способом мы находим за время O(log i) левую и правую опорные прямые. После этого за время O(log i) мы можем удалить все выпуклые вершины и сбалансируем дерево. Отсюда следует теорема:

Теорема 7. Выпуклая оболочка множества из N точек на плоскости может быть найдена с помощью открытого алгоритма за время ((N log N) и со временем коррекции ((log N).

Сравнительный анализ алгоритмов построения выпуклой оболочки

Так как теоретически показали, что время работы всех алгоритмов в среднем
O(log N), то следует ожидать при тестировании почти всегда результаты отличающиеся на константу.
Проведем исследования зависимости времени работы алгоритмов от размеров задачи при равномерном распределении точек:

[pic]

Рис. 5: Зависимость время выполнения алгоритмов при равномерном случайном расположении точек (Nq^.y)) then begin e:=q; cut(q,e); ins(b,e); end else begin e:=p; cut(p,e); ins(b,e); end; end; if pnil then begin e:=p; inss(b,e,e^.prev); end; if qnil then begin e:=q; inss(b,e,e^.prev); end; end; procedure sort2(var b:prec;e:prec); var p,q:prec; x:tp; begin if b=e then exit; if b^.next=e then begin if (b^.xabs(t^.x-x)+abs(t^.y-y))) then r:=t; t:=t^.n; until t=l2; l2:=r; l1^.p^.n:=nil; l2^.p^.n:=nil; r:=l1; l:=l2; ls:=nil; while (rnil) and (lnil) do begin if (r^.a(m^.x-p^.x)*(m^.n^.y-p^.y))) then begin l:=m; exit; end; if (n^.n=n) or

(((n^.n^.x-p^.x)*(n^.y-p^.y)=(n^.x-p^.x)*(n^.n^.y-p^.y)) and
(abs(n^.x-p^.x)=abs(n^.n^.x-p^.x)+abs(n^.n^.x-n^.x)) and (abs(n^.y- p^.y)=abs(n^.n^.y-p^.y)+abs(n^.n^.y-n^.y))) or

(((n^.p^.x-p^.x)*(n^.y-p^.y)>(n^.x-p^.x)*(n^.p^.y-p^.y)) and
((n^.n^.x-p^.x)*(n^.y-p^.y)>(n^.x-p^.x)*(n^.n^.y-p^.y))) then begin l:=n; exit; end; if m^.nm then begin fm:=((m^.n^.x-p^.x)*(m^.y-p^.y)>(m^.x-p^.x)*(m^.n^.y-p^.y)) or

((m^.p^.x-p^.x)*(m^.y-p^.y)(n^.x-p^.x)*(n^.n^.y-p^.y)) or

((n^.p^.x-p^.x)*(n^.y-p^.y)(n^.x-p^.x)*(m^.y-p^.y);

if (m^.lnil) and ((f and not(fn)) or (not(f) and fm)) then getleft(m^.l,n,l) else if m^.rnil then getleft(m^.r,m^.n,l); end; end; procedure getright(m,n:prec;var l:prec); var fm,fn,f:boolean; begin l:=nil; if ((p^.x=m^.x) and (p^.y=m^.y)) or ((p^.x=n^.x) and (p^.y=n^.y)) then exit; if ((p^.x=m^.p^.x) and (p^.y=m^.p^.y)) or ((p^.x=n^.p^.x) and
(p^.y=n^.p^.y)) then exit; if (m^.n=m) or

(((m^.p^.x-p^.x)*(m^.y-p^.y)=(m^.x-p^.x)*(m^.p^.y-p^.y)) and
(abs(m^.x-p^.x)=abs(m^.p^.x-p^.x)+abs(m^.p^.x-m^.x)) and (abs(m^.y- p^.y)=abs(m^.p^.y-p^.y)+abs(m^.p^.y-m^.y))) or

Поделитесь этой записью или добавьте в закладки