Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

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

  • Комбинаторная вычислительная геометрия, которая имеет дело с коллекциями дискретных объектов или определяется в дискретных терминах: точки, линии, многоугольники, многогранники и т. Д., И используются алгоритмы дискретного / комбинаторного характера.
  • Численная вычислительная геометрия, также известная как геометрическое моделирование и компьютерное геометрическое проектирование (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, FP: "Computational geometry - a overview". IEEE Trans. на компьютерах . Vol. 33, № 12, стр. 1072–1101 (1984). Он ориентирован на двумерные проблемы, но также имеет отступления в более высокие измерения. [1] [2]
    Первоначальным ядром книги была докторская диссертация М.И.Шамоса, которую еще один пионер в этой области, Рональд Грэм, предложил превратить в книгу .
    Введение охватывает историю области, основные структуры данных и необходимые понятия из теории вычислений и геометрии.
    Последующие разделы охватывают геометрический поиск (определение местоположения точки , поиск по дальности ), вычисление выпуклой оболочки , проблемы, связанные с близостью ( ближайшие точки , вычисление и приложения диаграммы Вороного , евклидово минимальное остовное дерево , триангуляции и т. Д.), Задачи геометрического пересечения , алгоритмы для наборов изотетических прямоугольников
  • Герберт Эдельсбруннер (1987). Алгоритмы комбинаторной геометрии . Springer-Verlag . ISBN 0-89791-517-8.
    Монография представляет собой довольно продвинутое изложение проблем и подходов в вычислительной геометрии, сфокусированных на роли расположения гиперплоскостей , которые, как показано, составляют базовую базовую комбинаторно-геометрическую структуру в определенных областях данной области. Основная целевая аудитория - активные исследователи-теоретики в данной области, а не разработчики приложений. В отличие от большинства книг по вычислительной геометрии, посвященных 2- и 3-мерным задачам (где находится большинство приложений вычислительной геометрии), цель книги - рассматривать ее предмет в общем многомерном контексте. [3]
  • Марк де Берг , Отфрид Чеонг , Марк ван Кревельд и Марк Овермарс (2008). Вычислительная геометрия (3-е исправленное изд.). Springer-Verlag . ISBN 3-540-77973-6. 1-е издание (1997 г.): ISBN 3-540-61270-X . 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). Дискретная и вычислительная геометрия . Издательство Принстонского университета . ISBN 978-0-691-14553-2.CS1 maint: использует параметр авторов ( ссылка )
  • Джим Арлоу (2014). Интерактивная вычислительная геометрия - таксономический подход . Mountain Way Limited . 1-е издание: ISBN 978-0-9572928-2-6 . 
    Эта книга представляет собой интерактивное введение в фундаментальные алгоритмы вычислительной геометрии в формате интерактивного документа, который можно просматривать с помощью программного обеспечения, основанного на системе Mathematica .

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

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

Ссылки [ править ]

  • Джейкоб Э. Гудман ; Джозеф О'Рурк , ред. (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 глав охватывают количественную геометрию, историю вычислительной геометрии, создание сеток, автоматическое создание геометрических доказательств, рандомизированные геометрические алгоритмы, проблемы дерева Штейнера, диаграммы Вороного и триангуляции Делоне, решение ограничений, сплайн-поверхности, проектирование сетей и численное моделирование. примитивы для геометрических вычислений.

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

Монографии [ править ]

  • ID Faux ; Майкл Дж. Пратт (1980). Вычислительная геометрия для проектирования и производства (математика и ее приложения) . Прентис Холл . ISBN 0-470-27069-1.
  • Алан Дэвис ; Филип Сэмюэлс (1996). Введение в вычислительную геометрию кривых и поверхностей . Издательство Оксфордского университета . ISBN 0-19-853695-X.
  • Жан-Даниэль Буассонна ; Моник Тейо (2006). Эффективная вычислительная геометрия для кривых и поверхностей ( Серия «Математика и визуализация»,  ред.). Springer Verlag . ISBN 3-540-33258-8.
  • Джеральд Фарин (1988). Кривые и поверхности для компьютерного геометрического проектирования . Академическая пресса . ISBN 0-12-249050-9.
  • Ричард Х. Бартельс , Джон К. Битти и Брайан А. Барски (1987). Сплайны для использования в компьютерной графике и геометрическом моделировании . Морган Кауфманн . ISBN 0-934613-27-3.CS1 maint: uses authors parameter (link)
  • Кристоф М. Хоффманн (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. (Errata: IEEE Tr. C. vol.34, No. 6, 1985) Этот 30-страничный документ, хотя и не книга, представляет исторический интерес, поскольку он был первым всеобъемлющим обзором, моментальным снимком зарождающейся дисциплины в 1984 г. Библиография из 354 пунктов.
  • Джордж Т. Хейнеман; Гэри Поллис и Стэнли Селкоу (2008). «Глава 9: Вычислительная геометрия». Об алгоритмах в двух словах . Oreilly Media . С. 251–298. ISBN 978-0-596-51624-6. - Эта книга имеет связанный репозиторий кода с полными реализациями Java.

Конференции [ править ]

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

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

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

Сборники бумаги [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

  1. ^ MR 0805539 , MR 1004870
  2. ^ Zbl 0575.68037 , Zbl 0575.68059  
  3. ^ Обзор книги Edelsbrunner в ZBL 0634.52001 
  4. ^ Обзоры в Zbl 0877.68001 (1-е изд.), Zbl 0939.68134 (2-е изд.)  
  5. ↑ О книге де Берга, ван Кревельда, Овермарса и Шварцкопфа
  6. ^ Обзор Справочника по вычислительной геометрии в геомбинаторике , январь 2005 г.
  7. ↑ С форзаца книги.

Внешние ссылки [ править ]

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