Вычислительная геометрия
книга

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

Автор: Марк Берг, Отфрид Чеонг , Марк Кревельд, Марк Овермарс

Форматы: PDF

Издательство: ДМК Пресс

Год: 2017

Место издания: Москва

ISBN: 978-5-97060-406-9

Страниц: 438

Артикул: 94571

Возрастная маркировка: 16+

цена: 890
Купить и скачать Читать фрагмент

Перед вами хорошо известное введение в вычислительную геометрию. Основной упор в книге сделан на алгоритмах в виде, доступном широкой аудитории. Все методы и решения, разрабатываемые в рамках вычислительной геометрии, связаны с конкретными применениями в робототехнике, компьютерной графике, САПР/АСУП и геоинформационных системах. Для большинства рассмотренных геометрических задач приводится одно, наиболее оптимальное решение. Рассмотрены все основные, а также ряд специальных тем вычислительной геометрии. Издание предназначено студентам, аспирантам, а также разработчикам программного обеспечения, имеющих лишь базовую подготовку в области алгоритмов.

Предисловие
ГЛАВА 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. Упражнения
Список литературы
Предметный указатель

Все отзывы о книге

Чтобы оставить отзыв, зарегистрируйтесь или войдите

Рецензии на книгу

Чтобы писать рецензии и получать вознаграждения за рекомендации книг, станьте экспертом