Алгоритм побудови опуклоi оболонки на площинi

КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

ІМЕНІ ТАРАСА ШЕВЧЕНКА

Факультет комп'ютерних наук та кібернетики

Кафедра теорії та технологій програмування

РЕФЕРАТ

з дисципліни «Соціально-політичні студії»

на тему:

«АЛГОРИТМ ПОБУДОВИ ОПУКЛОЇ ОБОЛОНКИ НА ПЛОЩИНІ»

Виконала:

студентка групи ТТП-4

Іванова Олена

                                                            Київ - 2022

ЗМІСТ

Вступ        2

1. Плоский корпус....................................................................................................................2

2. Нижня межа обчислювальної складності..........................................................................3

3. Оптимальні чутливі до виходу алгоритми.........................................................................4

4. Види алгоритмів...................................................................................................................4

5. Евристика Акла та Туссена.................................................................................................6

6. Онлайн і динамічні проблеми опуклої оболонки..............................................................6

7. Швидкі методи побудови опуклої оболонки.....................................................................7

Висновки..................................................................................................................................8

Список використаних джерел............................................................................................10

Вступ

Метою даної роботи є аналіз алгоритмів побудови опуклої оболонки на площині. Також обговоримо проблему побудови опуклої оболонки з множини точок, розглянемо точки, задані на площині.

Алгоритми, які будують опуклі оболонки різних об’єктів, мають широке застосування в математиці та інформатиці. У обчислювальній геометрії пропонуються численні алгоритми для обчислення опуклої оболонки скінченної множини точок з різною обчислювальною складністю.

Обчислення опуклої оболонки означає, що будується недвозначне та ефективне представлення необхідної опуклої форми. Складність відповідних алгоритмів зазвичай оцінюється через n, кількість вхідних точок, а іноді також через h, кількість точок на опуклій оболонці.

Поняття опуклої оболонки є досить простим та інтуїтивно зрозумілим. Якщо уявити гумовий шнур, натягнутий на безліч точок, це і буде опукла оболонка для безлічі точок. Незважаючи на свою простоту, воно не конструктивне, тому в роботі будуть розглянуті способи побудови ефективних алгоритмів для побудови опуклої оболонки.

Опукла оболонка є повсюдно поширеною структурою в обчислювальній геометрії. Незважаючи на те, що це сам по собі корисний інструмент, він також корисний при побудові інших структур, таких як діаграми, і в таких програмах, як аналіз зображень без нагляду.

1. Плоский корпус

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

Якщо не всі точки знаходяться на одній прямій, то їх опукла оболонка є опуклим многокутником, вершинами якого є деякі точки вхідного набору. Найпоширенішим представленням є список його вершин, упорядкованих уздовж його кордону за годинниковою стрілкою або проти неї. У деяких додатках зручно представляти опуклий многокутник у вигляді перетину множини півплощин.

1. Нижня межа обчислювальної складності

Для кінцевого набору точок на площині нижня межа обчислювальної складності пошуку опуклої оболонки, представленої у вигляді опуклого многокутника, легко показати такою ж, як і для сортування за допомогою наступного скорочення.

Щоб сортувати набір  розглянемо набір точок на площині. Оскільки вони лежать на параболі, яка є опуклою кривою, легко помітити, що вершини опуклої оболонки, проходячи вздовж кордону, створюють відсортований порядок чисел . Зрозуміло, що для описаного перетворення чисел у точки з подальшим вилученням їх відсортованого порядку потрібен лінійний час. Тому в загальному випадку опукла оболонка з n точок не може бути обчислена швидше, ніж сортування.[pic 1][pic 2][pic 3]