Список книг по вычислительной геометрии

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

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

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

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

• Франко П. Препарата ; Майкл Ян Шамос (1985). Вычислительная геометрия. Введение . Спрингер-Верлаг . ISBN  0-387-96131-3 . 1-е издание; 2-е издание, исправленное и дополненное, 1988 г.: ISBN   3-540-96131-3 ; Русский перевод, 1989: ISBN   5-03-001041-6 .

  Книга представляет собой первую всеобъемлющую монографию уровня учебника для аспирантов, систематически освещающую фундаментальные аспекты развивающейся дисциплины вычислительной геометрии. Книга написана основоположниками этой области, и первое издание охватывает все основные события, произошедшие за предыдущие 10 лет. С точки зрения полноты ему предшествовала только обзорная статья 1984 года Ли Д. Т., Препарата Ф. П.: «Вычислительная геометрия - обзор». IEEE Транс. на компьютерах . Том. 33, № 12, стр. 1072–1101 (1984). Он сосредоточен на двумерных проблемах, но также имеет отступления в более высокие измерения.

  Первоначальной основой книги стала докторская диссертация М.И.Шамоса, которую предложил превратить в книгу еще один пионер в этой области Рональд Грэм .

  Введение охватывает историю этой области, основные структуры данных и необходимые понятия из теории вычислений и геометрии.

  Последующие разделы охватывают геометрический поиск ( расположение точки , поиск диапазона ), вычисление выпуклой оболочки , проблемы, связанные с близостью ( ближайшие точки , вычисление и применение диаграммы Вороного , евклидово минимальное остовное дерево , триангуляции и т. д.), геометрические задачи пересечения , алгоритмы. для наборов изотетических прямоугольников

• Герберт Эдельсбруннер (1987). Алгоритмы в комбинаторной геометрии . Спрингер-Верлаг . ISBN  0-89791-517-8 .

  Монография представляет собой довольно продвинутое изложение проблем и подходов в вычислительной геометрии, сосредоточенное на роли механизмов гиперплоскости , которые, как показано, составляют базовую комбинаторно-геометрическую структуру в определенных областях этой области. Основная целевая аудитория — активные исследователи-теоретики в этой области, а не разработчики приложений. В отличие от большинства книг по вычислительной геометрии, посвященных 2- и 3-мерным проблемам (где сосредоточено большинство приложений вычислительной геометрии), цель книги - рассмотреть ее предмет в общей многомерной обстановке.

• Марк де Берг ; Отфрид Чеонг ; Марк ван Кревелд ; Марк Овермарс (2008). Вычислительная геометрия (3-е исправленное изд.). Издательство Спрингер . ISBN  978-3-540-77973-5 . 1-е издание (1997 г.): ISBN   3-540-61270-X .

  Учебник представляет собой введение в вычислительную геометрию с точки зрения практического применения. Начиная с вводной главы, каждая из оставшихся 15 формулирует реальную прикладную задачу, формулирует основную геометрическую задачу и обсуждает методы вычислительной геометрии, полезные для ее решения, с алгоритмами, представленными в псевдокоде. В книге рассматривается в основном двух- и трехмерная геометрия. Цель книги — предоставить всестороннее введение в методы и подходы, а не передовые исследования в этой области: представленные алгоритмы предоставляют прозрачные и достаточно эффективные решения, основанные на фундаментальных «строительных блоках» вычислительной геометрии.

  Книга состоит из следующих глав (в которых представлены как решения темы названия, так и ее применения): «Вычислительная геометрия (Введение)», «Пересечение отрезков прямой», «Триангуляция многоугольника», «Линейное программирование», «Поиск ортогонального диапазона». ", "Расположение точки", "Диаграммы Вороного", "Расположение и двойственность", "Триангуляции Делоне", "Более геометрические структуры данных", "Выпуклые оболочки", "Разбиение двоичного пространства", "Планирование движения робота", "Кваддеревья" , «Графики видимости», «Симплексный поиск по диапазону».

• Жан-Даниэль Буассонна ; Мариетт Ивинец (1998). Алгоритмическая геометрия . Издательство Кембриджского университета . ISBN  0-521-56529-4 . Перевод французского издания 1995 года.
• Джозеф О'Рурк (1998). Вычислительная геометрия в C (2-е изд.). Издательство Кембриджского университета . ISBN  0-521-64976-5 .
• Сатьян Девадосс ; Джозеф О'Рурк (2011). Дискретная и вычислительная геометрия . Издательство Принстонского университета . ISBN  978-0-691-14553-2 .
• Джим Арлоу (2014). Интерактивная вычислительная геометрия — таксономический подход . Маунтин Вэй Лимитед . ISBN  978-0-9572928-2-6 . 1-е издание.

  Эта книга представляет собой интерактивное введение в фундаментальные алгоритмы вычислительной геометрии, отформатированное в виде интерактивного документа, доступного для просмотра с помощью программного обеспечения на базе Mathematica .

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

• Селим Г. Акль ; Келли А. Лайонс (1993). Параллельная вычислительная геометрия . Прентис-Холл . ISBN  0-13-652017-0 .
• Франц Ауренхаммер ; Рольф Кляйн; Дер-Цай Ли (2013). Диаграммы Вороного и триангуляции Делоне . Всемирная научная.
• Эрик Д. Демейн ; Джозеф О'Рурк (2007). Геометрические алгоритмы складывания: связи, оригами, многогранники . Издательство Кембриджского университета. ISBN  978-0-521-85757-4 .
• Эфи Фогель; Дэн Гальперин ; Рон Вейн (2012). Механизмы CGAL и их применение, пошаговое руководство . Спрингер-Верлаг . ISBN  978-3-642-17283-0 .
• Клара И. Грима и Альберто Маркес (1990). Вычислительная геометрия на поверхностях: выполнение вычислительной геометрии на цилиндре, сфере, торе и конусе . Академическое издательство Kluwer . ISBN  1-4020-0202-5 .
• Фаджи Ли; Рейнхард Клетте (2011). Евклидовы кратчайшие пути . Издательство Спрингер . ISBN  978-1-4471-2255-5 .
• Курт Мельхорн (1984). Структуры данных и эффективные алгоритмы 3: Многомерный поиск и вычислительная геометрия . Спрингер-Верлаг .
• Курт Мельхорн ; Стефан Нэхер (1999). LEDA, платформа для комбинаторных и геометрических вычислений . Издательство Кембриджского университета . ISBN  0-521-56329-1 .
• Кетан Малмули (1994). Вычислительная геометрия: введение через рандомизированные алгоритмы . Прентис-Холл . ISBN  0-13-336363-5 .
• Гири Нарасимхан; Мишель Смид (2007). Геометрические гаечные сети . Издательство Кембриджского университета . ISBN  978-0-521-81513-0 .
• Ацуюки Окабе; Барри Бутс; Кокичи Сугихара ; Сунг Нок Чиу (2000). Пространственные замощения: концепции и применение диаграмм Вороного (2-е изд.). Джон Уайли и сыновья.
• Джозеф О'Рурк (1987). Теоремы и алгоритмы художественной галереи . Издательство Оксфордского университета .
• Янош Пах ; Панкадж К. Агарвал (1995). Комбинаторная геометрия . Джон Уайли и сыновья . ISBN  0-471-58890-3 .
• Ханан Самет (1990). Проектирование и анализ пространственных структур данных . Аддисон-Уэсли . ISBN  978-0-201-50255-8 .
• Филип Дж. Шнайдер; Дэвид Х. Эберли (2002). Геометрические инструменты для компьютерной графики . Морган Кауфманн .
• Миша Шарир ; Панкадж К. Агарвал (1995). Последовательности Давенпорта–Шинцеля и их геометрические приложения . Издательство Кембриджского университета . ISBN  0-521-47025-0 .
• Гош, Субир Кумар (2007). Алгоритмы видимости на плоскости . Издательство Кембриджского университета . ISBN  978-0-521-87574-5 .
• Буассонна, Жан-Даниэль ; Шазаль, Фредерик; Ивинец, Мариетта (2018). Геометрический и топологический вывод . Кембриджские тексты по прикладной математике. Издательство Кембриджского университета .

Ссылки

• Джейкоб Э. Гудман ; Джозеф О'Рурк , ред. (2004) [1997]. Справочник по дискретной и вычислительной геометрии . Северная Голландия . ISBN  0-8493-8524-5 . 1-е издание: 2-е издание: ISBN   1-58488-301-4 .

  По своей организации книга напоминает классический справочник по алгоритмам «Введение в алгоритмы» , по своей полноте ограничивается только дискретной и вычислительной геометрией, вычислительной топологией , а также широким спектром их приложений. Второе издание расширяет книгу вдвое: добавлено 14 глав и обновлены старые главы. Его 65 глав (более 1500 страниц) написаны большой командой активных исследователей в этой области.

• Йорг-Рюдигер Зак ; Хорхе Уррутиа (1998). Справочник по вычислительной геометрии . Северная Голландия . ISBN  0-444-82537-1 . 1-е издание: 2-е издание (2000 г.): 1-584-88301-4.

  Справочник содержит обзорные главы по классическим и новым исследованиям геометрических алгоритмов: расположение гиперплоскостей, диаграммы Вороного, геометрические и пространственные структуры данных, разложение полигонов, рандомизированные алгоритмы, дерандомизация, параллельная вычислительная геометрия (детерминированная и рандомизированная), видимость, художественная галерея и проблемы освещения. , проблемы ближайших точек , проблемы расстояния связи , сходство геометрических объектов, последовательности Давенпорта – Шинцеля , остовные деревья и гаечные ключи для геометрических графов, надежность и численные проблемы для геометрических алгоритмов, анимации и рисования графиков.

  Кроме того, в книге рассматриваются приложения геометрических алгоритмов в таких областях, как географические информационные системы , геометрический кратчайший путь, оптимизация сети и построение сетки.

• Дин-Чжу Ду ; Фрэнк Хван (1995). Вычисления в евклидовой геометрии . Серия заметок лекций по вычислительной технике. Том. 4 (2-е изд.). Всемирная научная. ISBN  981-02-1876-1 .

  «Эта книга представляет собой сборник обзоров и исследовательских статей о последних достижениях в области вычислительной евклидовой геометрии». Его 11 глав охватывают количественную геометрию, историю вычислительной геометрии, создание сеток, автоматическое создание геометрических доказательств, рандомизированные геометрические алгоритмы, задачи дерева Штейнера, диаграммы Вороного и триангуляции Делоне, решение ограничений, сплайн-поверхности, проектирование сетей и числовые примитивы для геометрических задач. вычисления.

геометрическое моделирование, автоматизированное геометрическое проектирование

Монографии

• идентификатор фальшивый ; Майкл Дж. Пратт (1980). Вычислительная геометрия для проектирования и производства (Математика и ее приложения) . Прентис Холл . ISBN  0-470-27069-1 .
• Алан Дэвис ; Филип Сэмюэлс (1996). Введение в вычислительную геометрию кривых и поверхностей . Издательство Оксфордского университета . ISBN  0-19-853695-Х .
• Жан-Даниэль Буассонна ; Моник Тейо (2006). Эффективная вычислительная геометрия для кривых и поверхностей ( под ред. Серии «Математика и визуализация» ). Спрингер Верлаг . ISBN  3-540-33258-8 .
• Джеральд Фарин (1988). Кривые и поверхности для компьютерного геометрического проектирования . Академическая пресса . ISBN  0-12-249050-9 .
• Ричард Х. Бартельс ; Джон С. Битти ; Брайан А. Барски (1987). Сплайны для использования в компьютерной графике и геометрическом моделировании . Морган Кауфманн . ISBN  0-934613-27-3 .
• Кристоф М. Хоффманн (1989). Геометрическое и твердотельное моделирование: Введение . Морган Кауфманн . ISBN  1-55860-067-1 . Книга больше не издается. Его основные главы:
  • Основные понятия
  • Булевы операции над представлением границ
  • Надежные и безошибочные геометрические операции
  • Представление изогнутых ребер и граней
  • Пересечения поверхностей
  • на основе Грёбнера Техники

Другое

• Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стейн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 1990. ISBN   0-262-03293-7 . — В этой книге есть глава, посвященная геометрическим алгоритмам.
• Фрэнк Нильсен . Визуальные вычисления: графика, зрение и геометрия , Charles River Media, 2005. ISBN   1-58450-427-7 — Эта книга сочетает в себе графику, машинное зрение и геометрические вычисления и предназначена для студентов продвинутого уровня и профессионалов в области разработки игр и графики. Включает краткий код C++ для распространенных задач.
• Джеффри Уллман , Вычислительные аспекты СБИС , Computer Science Press, 1984, ISBN   0-914894-95-1 — Глава 9: «Алгоритмы для инструментов проектирования СБИС» описывает алгоритмы операций с многоугольниками, участвующих в автоматизации проектирования электроники ( проверка правил проектирования , извлечение цепей , размещение и маршрутизация ).
• Д.Т. Ли , Франко П. Препарата , «Вычислительная геометрия — обзор», IEEE Trans. Компьютеры , том 33, вып. 12, 1984, 1072–1101. (Ошибки: IEEE Tr. C. vol.34, № 6, 1985 г.) Хотя эта 30-страничная статья и не является книгой, она представляет исторический интерес, поскольку это было первое всестороннее освещение, снимок 1984 г. Библиография из 354 пунктов.
• Джордж Т. Хайнеман; Гэри Поллис и Стэнли Селкоу (2008). «Глава 9: Вычислительная геометрия». Коротко об алгоритмах . Орейли Медиа . стр. 251–298. ISBN  978-0-596-51624-6 . - Эта книга связана с репозиторием кода с полными реализациями Java.

Конференции

• Ежегодный симпозиум по вычислительной геометрии (SoCG)
• Канадская конференция по вычислительной геометрии ( CCCG )
• Японская конференция по дискретной и вычислительной геометрии ( JCDCG )

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

• Симпозиум ACM-SIAM по дискретным алгоритмам (SODA)
• Ежегодный симпозиум ACM по теории вычислений (STOC)
• Ежегодный симпозиум IEEE по основам компьютерных наук (FOCS)
• Ежегодная Аллертонская конференция по коммуникациям, управлению и вычислениям ( ACCC )

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

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

См. также

• Список важных публикаций по математике

Внешние ссылки

• Страницы вычислительной геометрии