Вычислительная геометрия. Алгоритмы и приложения

Предисловие
ГЛАВА 1. Вычислительная геометрия
Введение
1.1. Пример: выпуклые оболочки
1.2. Вырожденность и устойчивость
1.3. Области применения
1.4. Замечания
1.5. Упражнения
ГЛАВА 2. Пересечение отрезков
Наложение тематических карт
2.1. Пересечение отрезков прямых
2.2. Двусвязный список ребер
2.3. Вычисления наложения двух разбиений
2.4. Булевы операции
2.5. Замечания
2.6. Упражнения
ГЛАВА 3. Триангуляция многоугольника
Охрана картинной галереи
3.1. Охрана и триангуляции
3.2. Разбиение многоугольника на монотонные
части
3.3. Триангуляция монотонного многоугольника
3.4. Замечания
3.5. Упражнения
ГЛАВА 4. Линейное программированиех
Литейные формы
4.1. Геометрия отливки
4.2. Пересечение полуплоскостей
4.3. Инкрементное линейное программирование
4.4. Рандомизированное линейное
программирование
4.5. Неограниченные линейные программы
4.6*. Линейное программирование в многомерных
пространствах
4.7*. Минимальная описанная окружность
4.8. Замечания
4.9. Упражнения
ГЛАВА 5. Поиск в ортогональных диапазонах
Запрос к базе данных
5.1. Одномерный поиск по диапазону
5.2. Kd-деревья
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. Замечания
7.6. Упражнения
ГЛАВА 8. Конфигурации и двойственность
Избыточная выборка в трассировке лучей
8.1. Вычисление отклонения
8.2. Двойственность
8.3. Конфигурации прямых
8.4. Уровни и отклонение
8.5. Замечания
8.6. Упражнения
ГЛАВА 9. Триангуляции Делоне
Интерполяция высоты
9.1. Триангуляции множеств точек на плоскости
9.2. Триангуляция Делоне
9.3. Вычисление триангуляции Делоне
9.4. Анализ
9.5.* Общая схема рандомизированных алгоритмов
9.6. Замечания
9.7. Упражнения
ГЛАВА 10. Другие геометрические структуры
данных
Оконные запросы
10.1. Деревья интервалов
10.2. Приоритетные деревья поиска
10.3. Деревья отрезков
10.4. Замечания
10.5. Упражнения
ГЛАВА 11. Выпуклые оболочки
Приготовление смесей
11.1. Сложность выпуклых оболочек в трехмерном
пространстве
11.2. Вычисление выпуклых оболочек в трехмерном
пространстве
11.3.* Анализ
11.4.* Выпуклые оболочки и пересечение
полупространств
11.5.* И снова о диаграммах Вороного
11.6. Замечания
11.7. Упражнения
ГЛАВА 12. Двоичные разбиения пространства
Алгоритм художника
12.1. Определение BSP-дерева
12.2. BSP-деревья и алгоритм художника
12.3. Построение BSP-дерева
12.4.* Размер BSP-дерева в трехмерном
пространстве
12.5. BSP-деревья для сцен низкой плотности
12.6. Замечания
12.7. Упражнения
ГЛАВА 13. Планирование движения робота
Попасть туда, куда хочешь
13.1. Рабочее пространство и конфигурационное
пространство
13.2. Точечный робот
13.3. Суммы Минковского
13.4. Планирование движения поступательно
перемещающегося робота
13.5.* Планирование движения с вращением
13.6. Замечания
13.7. Упражнения
ГЛАВА 14. Квадродеревья
Генерация неравномерных сеток
14.1. Равномерные и неравномерные сетки
14.2. Квадродеревья для множеств точек
14.3. От квадродеревьев к сеткам
14.4. Замечания
14.5. Упражнения
ГЛАВА 15. Графы видимости
Нахождение кратчайшего маршрута
15.1. Кратчайшие пути для точечного робота
15.2. Вычисление графа видимости
15.3. Кратчайшие пути для поступательно
перемещающегося многоугольного робота
15.4. Замечания
15.5. Упражнения
ГЛАВА 16. Поиск в симплициальных диапазонах
Еще об оконных запросах
16.1. Деревья разбиения
16.2. Многоуровневые деревья разбиения
16.3. Деревья сечений
16.4. Замечания
16.5. Упражнения
Список литературы
Предметный указатель