Де Берг М., Чеонг О., ван Кревельд М., Овермарс М. Вычислительная геометрия: Алгоритмы и приложения

3-е изд. — М.: ДМК Пресс, 2017. — 438 c. — ISBN: 978-5-97060-406-9.Перед вами хорошо известное введение в вычислительную геометрию. Основной упор в книге сделан на алгоритмах в виде, доступном широкой аудитории. Все методы и решения, разрабатываемые в рамках вычислительной геометрии, связаны с конкретными применениями в робототехнике, компьютерной графике, САПР/АСУП и геоинформационных системах. Для большинства рассмотренных геометрических задач приводится одно, наиболее оптимальное решение. Рассмотрены все основные, а также ряд специальных тем вычислительной геометрии. Издание предназначено студентам, аспирантам, а также разработчикам программного обеспечения, имеющих лишь базовую подготовку в области алгоритмов.
Оглавление
Предисловие
Вычислительная геометрия. Введение
Пересечение отрезков. Наложение тематических карт
Триангуляция многоугольника. Охрана картинной галереи
Линейное программирование. Литейные формы
Поиск в ортогональных диапазонах. Запрос к базе данных
Локализация точки. Где я нахожусь
Диаграммы Вороного. Задача о почтовом отделении
Конфигурации и двойственность. Избыточная выборка в трассировке лучей
Триангуляции Делоне. Интерполяция высоты
Другие геометрические структуры данных. Оконные запросы
Выпуклые оболочки. Приготовление смесей
Двоичные разбиения пространства. Алгоритм художника
Планирование движения робота. Попасть туда, куда хочешь
Квадродеревья. Генерация неравномерных сеток
Графы видимости. Нахождение кратчайшего маршрута
Поиск в симплициальных диапазонах.