Вычислительная геометрия - это раздел информатики, посвященный изучению алгоритмов, которые можно сформулировать в терминах геометрии . Некоторые чисто геометрические проблемы возникают из изучения вычислительных геометрических алгоритмов , и такие проблемы также считаются частью вычислительной геометрии. Хотя современная вычислительная геометрия возникла недавно, это одна из старейших областей вычислений с историей, уходящей корнями в глубокую древность.
Вычислительная сложность является центральным элементом вычислительной геометрии и имеет большое практическое значение, если алгоритмы используются на очень больших наборах данных, содержащих десятки или сотни миллионов точек. Для таких наборов разница между O ( n 2 ) и O ( n log n ) может быть разницей между днями и секундами вычислений.
Основным стимулом для развития вычислительной геометрии как дисциплины был прогресс в компьютерной графике и автоматизированном проектировании и производстве ( CAD / CAM ), но многие проблемы вычислительной геометрии имеют классическую природу и могут исходить из математической визуализации .
Другие важные приложения вычислительной геометрии включают робототехнику ( планирование движения и задачи видимости), географические информационные системы (ГИС) (геометрическое расположение и поиск, планирование маршрута), проектирование интегральных схем (проектирование и проверка геометрии ИС), автоматизированное проектирование (CAE). (создание сетки), компьютерное зрение ( 3D-реконструкция ).
Основные разделы вычислительной геометрии:
- Комбинаторная вычислительная геометрия , также называемая алгоритмической геометрией , которая рассматривает геометрические объекты как дискретные объекты. Основополагающая книга Препараты и Шамоса датирует первое использование термина «вычислительная геометрия» в этом смысле 1975 годом [1].
- Числовая вычислительная геометрия , также называемая машинной геометрией , компьютерным геометрическим проектированием (CAGD) или геометрическим моделированием , которое в первую очередь занимается представлением реальных объектов в формах, подходящих для компьютерных вычислений в системах CAD / CAM. Эту ветвь можно рассматривать как дальнейшее развитие начертательной геометрии и часто считают ветвью компьютерной графики или САПР. Термин «вычислительная геометрия» в этом смысле используется с 1971 г. [2]
Комбинаторная вычислительная геометрия [ править ]
Основная цель исследований комбинаторной вычислительной геометрии - разработка эффективных алгоритмов и структур данных для решения задач, сформулированных в терминах основных геометрических объектов: точек, отрезков прямых, многоугольников , многогранников и т. Д.
Некоторые из этих проблем кажутся настолько простыми, что они вообще не рассматривались как проблемы до появления компьютеров . Рассмотрим, например, задачу ближайшей пары :
- Учитывая n точек на плоскости, найдите две точки с наименьшим расстоянием друг от друга.
Можно вычислить расстояния между всеми парами точек, из которых n (n-1) / 2 , а затем выбрать пару с наименьшим расстоянием. Этот алгоритм грубой силы занимает время O ( n 2 ); т.е. время его выполнения пропорционально квадрату количества точек. Классическим результатом вычислительной геометрии стала формулировка алгоритма, который требует O ( n log n ). Также были обнаружены рандомизированные алгоритмы , требующие O ( n ) ожидаемого времени [3], а также детерминированный алгоритм, который занимает O ( n log log n ) времени [4] .
Классы проблем [ править ]
Основные проблемы вычислительной геометрии можно классифицировать по-разному, в соответствии с различными критериями. Можно выделить следующие общие классы.
Статические проблемы [ править ]
В задачах этой категории вводятся некоторые входные данные, и необходимо построить или найти соответствующий выход. Вот некоторые фундаментальные проблемы этого типа:
- Выпуклая оболочка : по заданному набору точек найдите наименьший выпуклый многогранник / многоугольник, содержащий все точки.
- Пересечение линейных сегментов : Найдите точки пересечения между заданным набором линейных сегментов.
- Триангуляция Делоне
- Диаграмма Вороного : для заданного набора точек разделите пространство в соответствии с тем, какие точки наиболее близки к данным точкам.
- Линейное программирование
- Ближайшая пара точек : учитывая набор точек, найдите две, которые находятся на наименьшем расстоянии друг от друга.
- Самая дальняя пара точек
- Самый большой пустой круг : для данного набора точек найдите самый большой круг с центром внутри их выпуклой оболочки и не охватывающий ни одной из них.
- Евклидов кратчайший путь : соедините две точки в евклидовом пространстве (с многогранными препятствиями) кратчайшим путем.
- Триангуляция многоугольника: разделите внутреннюю часть многоугольника на треугольники.
- Генерация сетки
- Логические операции над полигонами
Вычислительная сложность для этого класса задач оценивается временем и пространством (памятью компьютера), необходимыми для решения данного экземпляра проблемы.
Проблемы с геометрическими запросами [ править ]
В задачах геометрического запроса, обычно известных как задачи геометрического поиска, входные данные состоят из двух частей: части пространства поиска и части запроса , которая варьируется в зависимости от экземпляра задачи. Пространство поиска обычно требует предварительной обработки , чтобы можно было эффективно ответить на несколько запросов.
Вот некоторые фундаментальные проблемы с геометрическими запросами:
- Поиск по диапазону : предварительная обработка набора точек для эффективного подсчета количества точек внутри области запроса.
- Расположение точки : учитывая разделение пространства на ячейки, создайте структуру данных, которая эффективно сообщает, в какой ячейке находится точка запроса.
- Ближайший сосед : предварительная обработка набора точек, чтобы эффективно найти, какая точка является ближайшей к точке запроса.
- Трассировка лучей : для заданного набора объектов в космосе создайте структуру данных, которая эффективно сообщает, какой объект луч запроса пересекает первым.
Если пространство поиска фиксировано, вычислительная сложность для этого класса задач обычно оценивается следующим образом:
- время и пространство, необходимые для построения структуры данных, в которой будет выполняться поиск
- время (а иногда и дополнительное пространство) для ответа на запросы.
В случае, когда разрешено изменять пространство поиска, см. « Динамические проблемы ».
Динамические проблемы [ править ]
Еще один важный класс - это динамические задачи , цель которых состоит в том, чтобы найти эффективный алгоритм для многократного поиска решения после каждой инкрементальной модификации входных данных (добавления или удаления входных геометрических элементов). Алгоритмы для задач этого типа обычно включают динамические структуры данных . Любая из вычислительных геометрических задач может быть преобразована в динамическую за счет увеличения времени обработки. Например, задача поиска диапазона может быть преобразована в задачу поиска динамического диапазона путем добавления и / или удаления точек. Динамическая выпуклая оболочка проблема состоит в том, чтобы отслеживать выпуклую оболочку, например, для динамически изменяющегося набора точек, т.е. пока входные точки вставляются или удаляются.
Вычислительная сложность для этого класса задач оценивается следующим образом:
- время и пространство, необходимые для построения структуры данных, в которой будет выполняться поиск
- время и пространство для изменения структуры данных поиска после постепенного изменения в пространстве поиска
- время (а иногда и дополнительное пространство) для ответа на запрос.
Варианты [ править ]
Некоторые проблемы можно рассматривать как относящиеся к любой из категорий, в зависимости от контекста. Например, рассмотрим следующую проблему.
- Точка в многоугольнике : решите, находится ли точка внутри или за пределами данного многоугольника.
Во многих приложениях эта проблема трактуется как однократная, т. Е. Относящаяся к первому классу. Например, во многих приложениях компьютерной графики общая проблема состоит в том, чтобы найти, в какой области экрана щелкнуть указателем . Однако в некоторых приложениях рассматриваемый многоугольник является неизменным, а точка представляет собой запрос. Например, входной многоугольник может представлять границу страны, а точка - положение самолета, и проблема состоит в том, чтобы определить, нарушил ли самолет границу. Наконец, в ранее упомянутом примере компьютерной графики в приложениях САПР изменяющиеся входные данные часто сохраняются в динамических структурах данных, которые могут использоваться для ускорения запросов «точка в многоугольнике».
В некоторых контекстах проблем с запросами есть разумные ожидания в отношении последовательности запросов, которые могут быть использованы либо для эффективных структур данных, либо для более точных оценок вычислительной сложности. Например, в некоторых случаях важно знать наихудший случай для общего времени для всей последовательности из N запросов, а не для одного запроса. См. Также « амортизированный анализ ».
Численная вычислительная геометрия [ править ]
Эта ветвь также известна как геометрическое моделирование и компьютерное геометрическое проектирование (CAGD).
Ключевыми проблемами являются моделирование и представление кривых и поверхностей.
Наиболее важными инструментами здесь являются параметрические кривые и параметрические поверхности , такие как кривые Безье , сплайновые кривые и поверхности. Важным непараметрическим подходом является метод установки уровня .
Сферы применения вычислительной геометрии включают судостроение, авиастроение и автомобилестроение.
См. Также [ править ]
- Список тем комбинаторной вычислительной геометрии
- Список тем по численной вычислительной геометрии
- CAD / CAM / CAE
- Список геометрических алгоритмов
- Твердотельное моделирование
- Вычислительная топология
- Компьютерное представление поверхностей
- Цифровая геометрия
- Дискретная геометрия (комбинаторная геометрия)
- Разделение пространства
- Трехкомплексный номер
- Надежные геометрические вычисления
- Викиверситет: Тема: Вычислительная геометрия
- Викиверситет: компьютерный геометрический дизайн
Ссылки [ править ]
- ^ Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия - Введение . Springer-Verlag . ISBN 0-387-96131-3. 1-е издание; 2-е издание, исправленное и расширенное, 1988 г.
- ^ А. Р. Форрест, "Вычислительная геометрия", Proc. Лондонское королевское общество , 321, серия 4, 187-195 (1971)
- ^ С. Хуллер и Ю. Матиас. Простой алгоритм рандомизированного сита для задачи ближайшей пары . Инф. Вычисл., 118 (1): 34–37,1995 ( PDF )
- ^ С. Форчун и Дж. Э. Хопкрофт. «Заметка об алгоритме ближайшего соседа Рабина». Письма об обработке информации, 8 (1), стр. 20–23, 1979 г.
Дальнейшее чтение [ править ]
- Список книг по вычислительной геометрии
Журналы [ править ]
Комбинаторная / алгоритмическая вычислительная геометрия [ править ]
Ниже приведен список основных журналов, публикующих исследования по геометрическим алгоритмам. Обратите внимание, с появлением журналов, специально посвященных вычислительной геометрии, доля геометрических публикаций в журналах общего назначения по информатике и компьютерной графике уменьшилась.
- Опросы ACM Computing
- Транзакции ACM на графике
- Acta Informatica
- Достижения в геометрии
- Алгоритмика
- Ars Combinatoria
- Вычислительная геометрия: теория и приложения
- Коммуникации ACM
- Компьютерный геометрический дизайн
- Компьютерная графика и приложения
- Мир компьютерной графики
- Дискретная и вычислительная геометрия
- Геомбинаторика
- Geometriae Dedicata
- Транзакции IEEE для графики
- Транзакции IEEE на компьютерах
- IEEE Transactions по анализу шаблонов и машинному анализу
- Письма об обработке информации
- Международный журнал вычислительной геометрии и приложений
- Журнал комбинаторной теории , серия B
- Журнал вычислительной геометрии
- Журнал дифференциальной геометрии
- Журнал ACM
- Журнал алгоритмов
- Журнал компьютерных и системных наук
- Наука управления
- Распознавание образов
- Письма с распознаванием образов
- Журнал SIAM по вычислениям
- Новости SIGACT ; представил "Столбец вычислительной геометрии" Джозефа О'Рурка
- Теоретическая информатика
- Визуальный компьютер
Внешние ссылки [ править ]
- Вычислительная геометрия
- Страницы вычислительной геометрии
- Геометрия в действии
- "Стратегические направления в вычислительной геометрии - отчет Рабочей группы" (1996)
- Журнал вычислительной геометрии
- (Ежегодная) Зимняя школа по вычислительной геометрии
- Лаборатория вычислительной геометрии