Вычислительная геометрия — это раздел компьютерной науки, посвященный изучению алгоритмов , которые могут быть сформулированы в терминах геометрии . Некоторые чисто геометрические проблемы возникают из изучения вычислительных геометрических алгоритмов, и такие проблемы также считаются частью вычислительной геометрии. Хотя современная вычислительная геометрия является недавней разработкой, она является одной из старейших областей вычислений с историей, уходящей в глубокую древность.
Вычислительная сложность является центральной для вычислительной геометрии, с большим практическим значением, если алгоритмы используются на очень больших наборах данных, содержащих десятки или сотни миллионов точек. Для таких наборов разница между O( n 2 ) и O( n log n ) может быть разницей между днями и секундами вычислений.
Основным толчком к развитию вычислительной геометрии как дисциплины послужил прогресс в области компьютерной графики и систем автоматизированного проектирования и производства ( CAD / CAM ), однако многие проблемы вычислительной геометрии носят классический характер и могут возникать в результате математической визуализации .
Другие важные приложения вычислительной геометрии включают робототехнику ( задачи планирования движения и видимости), географические информационные системы (ГИС) (геометрическое местоположение и поиск, планирование маршрутов), проектирование интегральных схем (проектирование и проверка геометрии ИС), компьютерное проектирование (CAE) (создание сеток) и компьютерное зрение ( 3D-реконструкция ).
Основными разделами вычислительной геометрии являются:
Хотя большинство алгоритмов вычислительной геометрии были разработаны (и разрабатываются) для электронных компьютеров, некоторые алгоритмы были разработаны для нетрадиционных компьютеров (например, оптических компьютеров [3] ).
Основной целью исследований в области комбинаторной вычислительной геометрии является разработка эффективных алгоритмов и структур данных для решения задач, сформулированных в терминах базовых геометрических объектов: точек, отрезков, многоугольников , многогранников и т. д.
Некоторые из этих проблем кажутся настолько простыми, что до появления компьютеров они вообще не считались проблемами . Рассмотрим, например, задачу о самой близкой паре :
Можно вычислить расстояния между всеми парами точек, которых n(n-1)/2 , а затем выбрать пару с наименьшим расстоянием. Этот алгоритм грубой силы занимает O ( n 2 ) времени; т. е. время его выполнения пропорционально квадрату числа точек. Классическим результатом в вычислительной геометрии была формулировка алгоритма, который занимает O( n log n ). Также были обнаружены рандомизированные алгоритмы , которые занимают O( n ) ожидаемого времени, [4] , а также детерминированный алгоритм, который занимает O( n log log n ) времени, [5] .
Основные проблемы вычислительной геометрии можно классифицировать по-разному, в соответствии с различными критериями. Можно выделить следующие общие классы.
В задачах этой категории дается некоторый ввод и соответствующий вывод необходимо построить или найти. Некоторые фундаментальные задачи этого типа:
Вычислительная сложность для этого класса задач оценивается по времени и пространству (памяти компьютера), необходимым для решения данного экземпляра задачи.
В геометрических задачах поиска , обычно известных как геометрические задачи поиска , входные данные состоят из двух частей: части пространства поиска и части запроса , которая варьируется в зависимости от экземпляров задачи. Пространство поиска обычно должно быть предварительно обработано таким образом, чтобы можно было эффективно отвечать на несколько запросов.
Некоторые фундаментальные проблемы геометрических запросов:
Если пространство поиска фиксировано, вычислительная сложность для этого класса задач обычно оценивается по формуле:
О случае, когда пространство поиска может изменяться, см. «Динамические задачи».
Еще один крупный класс — динамические задачи , в которых цель состоит в том, чтобы найти эффективный алгоритм для многократного нахождения решения после каждой инкрементной модификации входных данных (добавление или удаление входных геометрических элементов). Алгоритмы для задач этого типа обычно включают динамические структуры данных . Любая из вычислительных геометрических задач может быть преобразована в динамическую за счет увеличения времени обработки. Например, задача поиска в диапазоне может быть преобразована в задачу поиска в динамическом диапазоне, предусмотрев добавление и/или удаление точек. Задача динамической выпуклой оболочки заключается в отслеживании выпуклой оболочки, например, для динамически изменяющегося набора точек, т. е. пока входные точки вставляются или удаляются.
Вычислительная сложность для этого класса задач оценивается по формуле:
Некоторые проблемы можно рассматривать как принадлежащие к любой из категорий, в зависимости от контекста. Например, рассмотрим следующую проблему.
Во многих приложениях эта проблема рассматривается как однократная, т.е. относящаяся к первому классу. Например, во многих приложениях компьютерной графики распространенной проблемой является поиск того, какая область на экране была нажата указателем . Однако в некоторых приложениях рассматриваемый полигон является инвариантным, в то время как точка представляет собой запрос. Например, входной полигон может представлять границу страны, а точка - положение самолета, и проблема состоит в том, чтобы определить, нарушил ли самолет границу. Наконец, в ранее упомянутом примере компьютерной графики, в приложениях САПР изменяющиеся входные данные часто хранятся в динамических структурах данных, что может быть использовано для ускорения запросов точка-в-полигоне.
В некоторых контекстах проблем запросов существуют разумные ожидания относительно последовательности запросов, которые могут быть использованы либо для эффективных структур данных, либо для более точных оценок вычислительной сложности. Например, в некоторых случаях важно знать наихудший случай для общего времени для всей последовательности из N запросов, а не для одного запроса. См. также « амортизированный анализ ».
Это направление также известно как геометрическое моделирование и компьютерное геометрическое проектирование (CAGD).
Основными проблемами являются моделирование и представление кривых и поверхностей.
Наиболее важными инструментами здесь являются параметрические кривые и параметрические поверхности , такие как кривые Безье , сплайновые кривые и поверхности. Важным непараметрическим подходом является метод набора уровней .
Области применения вычислительной геометрии включают судостроение, авиастроение и автомобилестроение.
Ниже приведен список основных журналов, которые публиковали исследования в области геометрических алгоритмов. Обратите внимание, что с появлением журналов, специально посвященных вычислительной геометрии, доля геометрических публикаций в журналах по компьютерной науке общего назначения и компьютерной графике снизилась.
