Бібліографія: сторінки 107-111 (67 назв)

ВСТУП.....5
1. АЛГОРИТИМІЧНІ ІНСТРУМЕНТИ.....9
1.1. Аналіз задачі.....10
1.2. Установлення межі ефективності розв'язання задачі.....11
1.3. Визначення інструментів та стратегії розв'язання.....14
1.4. Створення та використання структур даних.....16
1.5. Типи структур даних.....16
2. ЗАДАЧІ НА ОХОПЛЕННЯ.....26
2.1. Побудова найменшого охоплюючого кола навколо множини точок (ОМК).....26
2.1.1. Алгоритм із використанням діаграми Вороного.....27
2.1.2. Алгоритм побудови базового трикутника.....30
2.1.3. Алгоритм на основі пошуку трьох базових точок.....32
2.2. Трикутник найменшої площі (ОМТ).....34
2.3. Побудова прямокутника найменшої площі, що містить задану множину точок (ОМП).....37
2.4. Побудова найменшого охоплюючого еліпса (ОМЕ).....46
2.4.1. Алгоритм побудови з використанням опуклої оболонки (варіант 1).....46
2.4.2. Алгоритм побудови з використанням опуклої оболонки (варіант 2).....51
2.4.3. Алгоритм побудови з використанням опуклої оболонки (варіант 3).....53
3. ЗАДАЧІ НА ВПИСУВАННЯ.....55
3.1. Побудова кола найбільшого радіуса, вписаного в опуклу оболонку (ВМКО).....55
3.1.1. Алгоритм на основі методу стискання сторін.....55
3.1.2. Алгоритм на основі подвійного тернарного пошуку.....59
3.2. Трикутник найбільшої площі, вписаний в опуклу оболонку (ВМТО (АОЗ1)).....63
3.2.1. Алгоритм простого перебирання.....63
3.2.2. Алгоритм бінарного пошуку вершин максимального трикутника.....66
3.3. Прямокутник найбільшої площі, вписаний в опуклу оболонку (ВМПО (А041)).....70
3.3.1. Алгоритм бінарного пошуку вершин максимального трикутника.....71
3.3.2. Алгоритм на основі методу січних прямих.....73
3.3.3. Алгоритм на основі методу prune-and-search для фіксованих точок.....79
3.4. Еліпс найбільшої площі, вписаний в опуклу оболонку (ВМЕО (ВО4)).....90
3.4.1. Алгоритм бінарного пошуку вершин максимального трикутника (варіант 1).....90
3.4.2. Алгоритм бінарного пошуку вершин максимального трикутника (варіант 2).....91
4. ЗАДАЧІ НА РОЗТАШУВАННЯ.....92
4.1. Найбільше порожнє коло РМК (АО5).....92
4.2. Найбільший порожній прямокутник РМП (АО6).....96
4.2.1. Алгоритм пошуку найбільшого порожнього прямокутника Орловського.....98
4.2.2. Алгоритм на основі діаграми Вороного.....100
4.2.3. Алгоритм з використанням тріангуляції.....105
ЛІТЕРАТУРА.....107

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