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

Вычислительная геометрия зародилась в области проектирования и анализа алгоритмов в конце 1970-х годов. Впоследствии она превратилась в самостоятельную дисциплину со своими журналами, конференциями и большим сообществом активно работающих исследователей.   Перед вами хорошо известное введение в вычислительную геометрию. В этой книге мы попытались представить современные алгоритмы в виде, доступном широкой аудитории. Книга задумана как учебник по курсу вычислительной геометрии, но может использоваться и для самообразования.   Все методы и решения, разрабатываемые в рамках вычислительной геометрии, связаны с конкретными применениями в робототехнике, компьютерной графике, САПР /АСУП и геоинформационных системах. Для большинства рассмотренных геометрических задач приводится одно, наиболее оптимальное решение. Рассмотрены все основные, а также ряд специальных тем вычислительной геометрии.   Каждая из шестнадцати глав (кроме введения) начинается с некоторой прикладной задачи. Эта задача переформулируется как чисто геометрическая, а затем решается методами вычислительной геометрии.   В конце каждой главы содержится раздел «Замечания». Здесь приводятся ссылки на источники приведенных в данной главе результатов, упоминаются другие решения, обобщения и усовершенствования и дается обзор литературы. Эти разделы можно пропустить, но они содержат полезную информацию для тех, кто хочет узнать больше о теме главы.