Список книг по вычислительной геометрии - List of books in computational geometry

Это список книг в вычислительная геометрия.Есть две основные, в основном неперекрывающиеся категории:

  • Комбинаторная вычислительная геометрия, которая имеет дело с коллекциями дискретных объектов или определена в дискретных терминах: точки, линии, многоугольники, многогранники и т. Д., И используются алгоритмы дискретного / комбинаторного характера.
  • Численная вычислительная геометрия, также известная как геометрическое моделирование и компьютерный геометрический дизайн (CAGD), который занимается моделированием форм реальных объектов в терминах кривых и поверхностей с алгебраическим представлением.

Комбинаторная вычислительная геометрия

Учебники общего назначения

  • Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия - Введение. Springer-Verlag. 1-е издание: ISBN  0-387-96131-3; 2-е издание, исправленное и расширенное, 1988 г .: ISBN  3-540-96131-3; Русский перевод, 1989 г .: ISBN  5-03-001041-6.CS1 maint: использует параметр авторов (связь)
    Книга является первой всеобъемлющей монографией на уровне учебника для выпускников, систематически освещающей фундаментальные аспекты формирующейся дисциплины вычислительной геометрии. Он написан основателями отрасли, и первое издание охватывало все основные события за предыдущие 10 лет. С точки зрения полноты ему предшествовала только обзорная статья 1984 г. Lee, D, T., Preparata, F.P .: "Computational geometry - a overview". IEEE Trans. на компьютерах. Vol. 33, № 12, стр. 1072–1101 (1984). Он ориентирован на двумерные проблемы, но также имеет отклонения в более высокие измерения.[1][2]
    Первоначальным ядром книги была докторская диссертация М.И. Шамоса, которую еще один пионер в этой области предложил превратить в книгу. Рональд Грэм.
    Введение охватывает историю области, основные структуры данных и необходимые понятия из теория вычислений и геометрия.
    Последующие разделы охватывают геометрический поиск (точка расположения, поиск диапазона ), выпуклый корпус вычисления, проблемы, связанные с близостью (ближайшие точки, расчет и приложения Диаграмма Вороного, Евклидово минимальное остовное дерево, триангуляции, так далее.), геометрические задачи пересечения, алгоритмы для наборов изотетические прямоугольники
  • Герберт Эдельсбруннер (1987). Алгоритмы комбинаторной геометрии. Springer-Verlag. ISBN  0-89791-517-8.
    Монография представляет собой довольно продвинутое изложение проблем и подходов в вычислительной геометрии с акцентом на роли схемы гиперплоскости, которые, как показано, составляют базовую базовую комбинаторно-геометрическую структуру в определенных областях поля. Основная целевая аудитория - активные исследователи-теоретики в данной области, а не разработчики приложений. В отличие от большинства книг по вычислительной геометрии, посвященных двумерным и трехмерным задачам (где находится большинство приложений вычислительной геометрии), цель книги - рассматривать ее предмет в многомерной среде.[3]
  • Марк де Берг, Отфрид Чеонг, Марк ван Кревельд, и Марк Овермарс (2008). Вычислительная геометрия (3-е изд. Изм.). Springer-Verlag. ISBN  3-540-77973-6. 1-е издание (1997 г.): ISBN  3-540-61270-Х.CS1 maint: использует параметр авторов (связь)
    Учебник представляет собой введение в вычислительную геометрию с точки зрения практических приложений. Начиная с вводной главы, каждая из оставшихся 15 формулирует реальную прикладную проблему, формулирует лежащую в основе геометрическую проблему и обсуждает методы вычислительной геометрии, полезные для ее решения, с алгоритмами, представленными в псевдокоде. В книге в основном рассматривается 2- и 3-мерная геометрия. Цель книги - дать исчерпывающее введение в методы и подходы, а не новейшие исследования в этой области: представленные алгоритмы обеспечивают прозрачные и достаточно эффективные решения, основанные на фундаментальных «строительных блоках» вычислительной геометрии.[4][5]
    Книга состоит из следующих глав (которые предоставляют как решения по теме названия, так и ее приложениям): «Вычислительная геометрия (Введение)», «Пересечение отрезка линии», «Триангуляция многоугольника», «Линейное программирование», «Поиск ортогонального диапазона. "," Местоположение точки "," Диаграммы Вороного "," Расположение и двойственность "," Триангуляции Делоне "," Другие геометрические структуры данных "," Выпуклые корпуса "," Бинарные пространственные разделы "," Планирование движения роботов "," Деревья квадратов " , «Графики видимости», «Односторонний поиск по диапазонам».
  • Жан-Даниэль Буассонна, Мариетт Ивинек (1998). Алгоритмическая геометрия. Издательство Кембриджского университета. ISBN  0-521-56529-4. Перевод французского издания 1995 года.CS1 maint: использует параметр авторов (связь)
  • Джозеф О'Рурк (1998). Вычислительная геометрия в C (2-е изд.). Издательство Кембриджского университета. ISBN  0-521-64976-5.
  • Сатьян Девадосс, Джозеф О'Рурк (2011). Дискретная и вычислительная геометрия. Princeton University Press. ISBN  978-0-691-14553-2.CS1 maint: использует параметр авторов (связь)
  • Джим Арлоу (2014). Интерактивная вычислительная геометрия - таксономический подход. Mountain Way Limited. 1-е издание: ISBN  978-0-9572928-2-6.
    Эта книга представляет собой интерактивное введение в фундаментальные алгоритмы вычислительной геометрии, оформленное в виде интерактивного документа, доступного для просмотра с помощью программного обеспечения на основе Mathematica.

Специализированные учебники и монографии

Рекомендации

  • Джейкоб Э. Гудман; Джозеф О'Рурк, ред. (2004) [1997]. Справочник по дискретной и вычислительной геометрии. Северная Голландия. 1-е издание: ISBN  0-8493-8524-5, 2-е издание: ISBN  1-58488-301-4.
    По своей организации книга напоминает классический справочник по алгоритмам, Введение в алгоритмы, в своей полноте, ограниченной только дискретной и вычислительной геометрией, вычислительная топология, а также широкий спектр их приложений. Второе издание расширяет книгу наполовину, добавляя 14 глав и обновляя старые главы. Его 65 глав (более 1500 страниц) написаны большой группой активных исследователей в этой области.[6]
  • Мешок Йорга-Рюдигера; Хорхе Уррутия (1998). Справочник по вычислительной геометрии. Северная Голландия. 1-е издание: ISBN  0-444-82537-1, 2-е издание (2000): 1-584-88301-4.
    Справочник содержит обзорные главы по классическим и новым исследованиям в области геометрических алгоритмов: расположение гиперплоскостей, диаграммы Вороного, геометрические и пространственные структуры данных, разложение многоугольников, рандомизированные алгоритмы, дерандомизация, параллельная вычислительная геометрия (детерминированная и рандомизированная), видимость, проблемы художественной галереи и освещения. , проблемы ближайшего пункта, расстояние связи проблемы, подобие геометрических объектов, Последовательности Давенпорта-Шинцеля, остовные деревья и гаечные ключи для геометрических графиков, надежности и числовых проблем для геометрических алгоритмов, анимации и рисования графиков.
    Кроме того, в книге рассматриваются применения геометрических алгоритмов в таких областях, как географические информационные системы, геометрический кратчайший путь и оптимизация сети и создание сетки.
  • Дин-Чжу Ду; Фрэнк Хван (1995). Вычисления в евклидовой геометрии. Серия заметок лекций по вычислениям. 4 (2-е изд.). World Scientific. ISBN  981-02-1876-1.
    «Эта книга представляет собой сборник обзоров и исследовательских статей о последних достижениях в области вычислительной евклидовой геометрии».[7] Его 11 глав охватывают количественную геометрию, историю вычислительной геометрии, создание сеток, автоматическое создание геометрических доказательств, рандомизированные геометрические алгоритмы, проблемы дерева Штейнера, диаграммы Вороного и триангуляции Делоне, решение ограничений, сплайн-поверхности, проектирование сетей и числовые примитивы для геометрических вычисление.

Численная вычислительная геометрия (геометрическое моделирование, компьютерное геометрическое проектирование)

Монографии

Другой

Конференции

На следующих конференциях широкого профиля было опубликовано множество основополагающих статей в этой области.

Коллекции бумаги

  • «Комбинаторная и вычислительная геометрия», ред. Джейкоб Э. Гудман, Янош Пах, Эмо Вельцль (ИИГС Публикации - Том 52), 2005 г., ISBN  0-521-84862-8.
    • 32 статьи, включая обзоры и исследовательские статьи по геометрическим схемам, многогранникам, упаковке, покрытию, дискретной выпуклости, геометрическим алгоритмам и их вычислительной сложности, а также комбинаторной сложности геометрических объектов.
  • «Обзоры по дискретной и вычислительной геометрии: двадцать лет спустя» (серия «Современная математика»), Американское математическое общество, 2008 г., ISBN  0-8218-4239-0

Смотрите также

Рекомендации

  1. ^ МИСТЕР0805539, МИСТЕР1004870
  2. ^ Zbl  0575.68037, Zbl  0575.68059
  3. ^ Рецензия на книгу Эдельсбруннера в Zbl  0634.52001
  4. ^ Обзоры в Zbl  0877.68001 (1-е изд.), Zbl  0939.68134 (2-е изд.)
  5. ^ О книге де Берга, ван Кревельда, Овермарса и Шварцкопфа
  6. ^ Обзор Справочник по вычислительной геометрии в Геомбинаторика, Январь 2005 г.
  7. ^ С форзаца книги.

внешняя ссылка