Наверх

Ф.Препарата, М.Шеймос, 1989 (Rus)
Вычислительная геометрия: Введение


Глава 1. ВВЕДЕНИЕ
1.1 Исторический обзор
1.2 Алгоритмические основы
1.3 Геометрические предпосылки
1.4 Модели вычислений


Глава 2. ГЕОМЕТРИЧЕСКИЙ ПОИСК
2.1 Введение в геометрический поиск
2.2 Задачи локализации точки
2.3 Задачи регионального поиска
2.4 Замечания и комментарии
2.5 Упражнения


Глава 3. ВЫПУКЛЫЕ ОБОЛОЧКИ: ОСНОВНЫЕ АЛГОРИТМЫ
3.1 Предварительные сведения
3.2 постановка задачи и нижние оценки сложности
3.3 Алгоритм построения выпуклой оболочки на плоскости
3.4 Выпуклые оболочки в пространствах размерности большей двух
3.5 Замечания и комментарии
3.6 Упражнения


Глава 4.
ВЫПУКЛЫЕ ОБОЛОЧКИ: РАСШИРЕНИЯ И ПРИЛОЖЕНИЯ
4.1 Расширения и варианты
4.2 Приложения в статистике
4.3 Замечания и комментарии
4.4 Упражнения


Глава 5. БЛИЗОСТЬ: ОСНОВНЫЕ АЛГОРИТМЫ
5.1 Набор задач
5.2 Задача о единственности элементов
5.3 Нижние оценки
5.4 Решение задачи о ближайшей паре методом "разделяй и властвуй"
5.5 Решение задачи о близости методом локусов; диаграмма Вороного
5.6 Решение задачи о близости с помощью диаграммы Вороного
5.7 Замечания и комментарии
5.8 Упражнения


Глава 6. БЛИЗОСТЬ: ВАРИАНТЫ И ОБОБЩЕНИЯ
6.1 Евклидовы минимальные остовные деревья
6.2 Планарные триангуляции
6.3 Обобщения диаграммы Вороного
6.4 Промежутки и покрытия
6.5 Замечания и комментарии
6.6 Упражнения


Глава 7. ПЕРЕСЕЧЕНИЯ
7.1 Примеры из приложений
7.2 Плоские приложения
7.3 Трехмерные приложения
7.4 Замечания и комментарии
7.5 Упражнения


Глава 8. ГЕОМЕТРИЯ ПРЯМОУГОЛЬНИКОВ
8.1 Некоторые приложения геометрии прямоугольников
8.2 Область применения результатов
8.3 Общие замечания по алгоритмам статического типа
8.4 Мера и периметр объединения прямоугольников
8.5 Контур объединения прямоугольников
8.6 Замыкание объединения прямоугольников
8.7 Внешний контур объединения прямоугольников
8.8 Пересечения прямоугольников и связанные с этим задачи
8.9 Замечания и комментарии
8.10 Упражнения


Литература

Именной указатель
Предметный указатель