Алгоритмы построения выпуклых оболочек множества точек на плоскости — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
Строка 45: Строка 45:
 
     return last;
 
     return last;
 
  };
 
  };
 +
 +
==Алгоритм Грэма==
 +
 +
==Алгоритм Эндрюса==
 +
 +
==Алгоритм Merge hull==
 +
 +
==Алгоритм Quick hull==
 +
 +
==Алгоритм Чена==
 +
'''Алгоритм Чена''' строит выпуклую оболочку конечного множества точек за <tex> O(n\log h) </tex> без вырожденных случаев, где <tex> h </tex> {{---}} количество точек в выпуклой оболочке. Основная идея заключается в том, чтобы разделить изначальное множество точек на группы по <tex> h </tex> элементов, построить выпуклые оболочки для каждой из групп, потом слить их в одну общую оболочку.
 +
 +
Алгоритм состоит из трех этапов
 +
# Разбиение исходного множества точек на группы по <tex> h </tex> элементов в каждой.
 +
# Построение выпуклых оболочек для групп.
 +
# Объединение выпуклых оболочек.
 +
 +
Предположим, что <tex> h </tex> нам известно.
 +
 +
Исходное множество точек можно разбивать на группы любым способом. Для простоты будем выделять группы просто по порядку. Первые <tex> h </tex> элементов {{---}} первая группа, следующие <tex> h </tex> элементов {{---}} вторая группа и так далее.
 +
 +
Строить выпуклые оболочки для групп можно с помощью алгоритма Грэма за <tex> O(h \log h) </tex>. Всего <tex> m </tex> групп, получаем суммарную асимптотику <tex> O(m h \log h) = O(n \log h). </tex>
 +
 +
Для объединения оболочек будем использовать обход по Джарвису. Самая левая точка точно лежит на общей внутренней оболочке. Научимся находить следующую точку. предположим, что мы умеем находить опорную прямую за <tex> O(\log h). </tex> Всего оболочек <tex> m </tex>. Получается, что точку мы умеем находить за <tex> O(m \log h). </tex> Всего точек на выпуклой оболочке <tex> h </tex>. Получаем объеденение оболочек за <tex> O(m h \log h) = O(n \log h) </tex>.
 +
 +
===Выбор числа h ===
 +
Заметим, что нам не обязательно знать точное значение <tex> h </tex>. Нас утроит любое значение <tex>\tilde h</tex>, такое что <tex>\log{\tilde h} = c \cdot \log h , c \ge 1 </tex>.
 +
 +
Будем использовать следующий метод:
 +
 +
Будем брать <tex> \tilde h =  2^{2^{t}}  , t = 1, 2...</tex>, пока <tex> \tilde h \le h</tex>. На каждую итерацию потребуется <tex> O(n \log {2 ^{2^{t}}}) = O(n \cdot 2 ^ {t})</tex>.
 +
 +
<tex dpi = 140> 2^{2^{t}} \ge h \Rightarrow t \ge \log \log h </tex>.
 +
 +
Посчитаем, сколько нам понадобится времени на поиск <tex> \tilde h </tex>
 +
 +
<tex dpi = 140> \sum_{1}^{\log \log h} n \cdot 2 ^ t = n \cdot \sum_{1}^{\log \log h} 2 ^ t = </tex>
 +
<tex dpi = 140> n \cdot 2 \cdot \frac{1 - 2^{\log \log h}}{1 - 2} = </tex>
 +
<tex dpi = 140> n \cdot 2^{\log \log h + 1} - n \le  n \cdot 2^{\log \log h + 1} = 2n \cdot \log h = O(n \cdot \log h)</tex>

Версия 16:52, 2 мая 2012

Эта статья находится в разработке!

Выпуклая оболочка множества точек

Определение:
Выпуклой оболочкой множества точек называется пересечение всех выпуклых множеств, содержащих все заданные точки.


Еще одно определение:

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


Будем рассматривать множество точек на плоскости и способы построения их выпуклых оболочек.

Некоторые свойства выпуклых оболочек:

  1. Экстремальные всегда принадлежат выпуклой оболочке.
  2. Для равномерно распределенных в прямоугольнике точек, выпуклая оболочка будет состоять из логарифма точек.
  3. Если в изначальном массиве точка на 0-й позиции будет самой левой, то после построения выпуклой оболочки in-place она останется там же.

Алгоритм Джарвиса

Алгоритм Джарвиса определяет последовательность точек, образующую выпуклую оболочку множества точек на плоскости. Так же известен как алгоритм "заворачивания подарка".

Время работы алгоритма — [math] O(h \cdot n) [/math], где [math] h [/math] — количество точек в выпуклой оболочке. В случае [math] h = n [/math] получаем [math] O(n ^ 2) [/math].

Алгоритм в силу своей простоты легко реализуется in-place.

Псевдокод

int jarvis(std::vector<dot> &dots)
{
   int last = 0;
   dots.push_back(dots[0]);
   int size = dots.size();
   do
   {
      for(int i = last + 2; i < size; i++)
      {
         std::swap(dots[last + 1], max_element(dots[last + 1], dots[i]));
      }
   }
   while(dots[last] != dots[0]);
   
   std::swap(dots[last], dots[size - 1]);
   dots.pop_back();
   
   return last;
};

Алгоритм Грэма

Алгоритм Эндрюса

Алгоритм Merge hull

Алгоритм Quick hull

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

Алгоритм Чена строит выпуклую оболочку конечного множества точек за [math] O(n\log h) [/math] без вырожденных случаев, где [math] h [/math] — количество точек в выпуклой оболочке. Основная идея заключается в том, чтобы разделить изначальное множество точек на группы по [math] h [/math] элементов, построить выпуклые оболочки для каждой из групп, потом слить их в одну общую оболочку.

Алгоритм состоит из трех этапов

  1. Разбиение исходного множества точек на группы по [math] h [/math] элементов в каждой.
  2. Построение выпуклых оболочек для групп.
  3. Объединение выпуклых оболочек.

Предположим, что [math] h [/math] нам известно.

Исходное множество точек можно разбивать на группы любым способом. Для простоты будем выделять группы просто по порядку. Первые [math] h [/math] элементов — первая группа, следующие [math] h [/math] элементов — вторая группа и так далее.

Строить выпуклые оболочки для групп можно с помощью алгоритма Грэма за [math] O(h \log h) [/math]. Всего [math] m [/math] групп, получаем суммарную асимптотику [math] O(m h \log h) = O(n \log h). [/math]

Для объединения оболочек будем использовать обход по Джарвису. Самая левая точка точно лежит на общей внутренней оболочке. Научимся находить следующую точку. предположим, что мы умеем находить опорную прямую за [math] O(\log h). [/math] Всего оболочек [math] m [/math]. Получается, что точку мы умеем находить за [math] O(m \log h). [/math] Всего точек на выпуклой оболочке [math] h [/math]. Получаем объеденение оболочек за [math] O(m h \log h) = O(n \log h) [/math].

Выбор числа h

Заметим, что нам не обязательно знать точное значение [math] h [/math]. Нас утроит любое значение [math]\tilde h[/math], такое что [math]\log{\tilde h} = c \cdot \log h , c \ge 1 [/math].

Будем использовать следующий метод:

Будем брать [math] \tilde h = 2^{2^{t}} , t = 1, 2...[/math], пока [math] \tilde h \le h[/math]. На каждую итерацию потребуется [math] O(n \log {2 ^{2^{t}}}) = O(n \cdot 2 ^ {t})[/math].

[math] 2^{2^{t}} \ge h \Rightarrow t \ge \log \log h [/math].

Посчитаем, сколько нам понадобится времени на поиск [math] \tilde h [/math]

[math] \sum_{1}^{\log \log h} n \cdot 2 ^ t = n \cdot \sum_{1}^{\log \log h} 2 ^ t = [/math] [math] n \cdot 2 \cdot \frac{1 - 2^{\log \log h}}{1 - 2} = [/math] [math] n \cdot 2^{\log \log h + 1} - n \le n \cdot 2^{\log \log h + 1} = 2n \cdot \log h = O(n \cdot \log h)[/math]