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

{{В разработке}}

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

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

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

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

Пусть нам дано конечное множество точек на плоскости <tex> D = \{d_0, d_1 \dots, d_n \}. </tex>  <tex> d_0 </tex> {{---}} cамая левая нижняя точка, лежит на выпуклой оболочке. 

Рассмотрим алгоритмы, позволяющие построить выпуклую оболочку <tex>D</tex>

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

Время работы алгоритма {{---}} <tex> O(h \cdot n) </tex>, где <tex> h </tex> {{---}} количество точек в выпуклой оболочке. В случае <tex> h = n </tex> получаем <tex> O(n ^ 2) </tex>.

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

===Описание Алгоритма===
Будем находить точку, с наименьшим полярным углом от предыдущей стороны. Если таких точек несколько - брать самую дальнюю. И так до тех пор, пока выпуклая оболочка не замкнется.

===Псевдокод===
 
 dot max_element(int j, int i)
 {
    if (left_turn(dots[j - 1], dots[j], dots[i]))
       return dots[j];
    else
       return dots[i];   
 }
 
 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(last + 1, i));
       }
    }
    while(dots[last] != dots[0]);
    
    std::swap(dots[last], dots[size - 1]);
    dots.pop_back();
    
    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>

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