ЗМІСТ
ПЕРЕДМОВА
ГЛАВА 1. ВСТУП
1.1. Складність алгоритмів
1.2. Моделі обчислень
1.3. Перетворення(зведення) задач
1.4. Оцінки складності деяких задач
1.5. Загальні означення
ГЛАВА 2. СТРУКТУРИ ДАНИХ
2.1. Структури даних
2.2. Дерево відрізків
2.3. Реберний список з подвійними зв'язками
ГЛАВА 3. ГЕОМЕТРИЧНИЙ ПОШУК
3.1. Вступ в геометричний пошук.
3.2. Задачі локалізації точки.
3.3.Задачі локалізації точки на планарному розбитті.
3.3.1. Метод смуг.
3.3.2. Метод ланцюгів.
3.3.3.Метод деталізації тріангуляції.
3.3.4. Метод трапецій.
3.4. Задачі регіонального пошуку.
3.4.1. Загальні зауваження.
3.4.2. Метод багатовимірного двійкового дерева.
3.4.3. Метод дерева регіонів.
ГЛАВА 4. ЗАДАЧІ ПОБУДОВИ ОПУКЛОЇ ОБОЛОНКИ.
4.1. Постановка задач опуклої оболонки.
4.2. Метод Грехема.
4.3. Метод Джарвіса.
4.4. Швидкі методи побудови опуклої оболонки.
4.5. Алгоритм " Розподіляй та володарюй".
4.6. Динамічні алгоритми побудови опуклої оболонки.
4.7. Узагальнення: підтримка динамічної опуклої оболонки.
4.8. Побудова опуклої оболонки простого многокутника.
4.8.1.Алгоритм апроксимації опуклої оболонки.
4.8.2.Побудова опуклої оболонки простого многокутника.
ГЛАВА 5. БЛИЗКІСТЬ. ОСНОВНІ АЛГОРИТМИ.
5.1. Основні задачі.
5.2. Нижні оцінки складності. Задачі прототипи.
5.3. Найближча пара - метод "Розподіляй та володарюй".
5.4. Діаграма Вороного. Властивості.
5.5. Побудова Діаграми Вороного.
5.6. Побудова розділяючого ланцюга.
5.7. Розв'язання задач про близькість за допомогою діаграми Вороного
ЛАБОРАТОРНІ РОБОТИ
Список лабораторних робіт.
ЛІТЕРАТУРА