Вычислительная геометрия — это раздел информатики, посвященный изучению алгоритмов, которые можно сформулировать в терминах геометрии . Некоторые чисто геометрические проблемы возникают в результате изучения вычислительных геометрических алгоритмов , и такие проблемы также считаются частью вычислительной геометрии. Хотя современная вычислительная геометрия возникла недавно, это одна из старейших областей вычислений, история которой уходит корнями в древность.
Сложность вычислений занимает центральное место в вычислительной геометрии и имеет большое практическое значение, если алгоритмы используются с очень большими наборами данных, содержащими десятки или сотни миллионов точек. Для таких наборов разница между 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).
Основными проблемами являются моделирование и представление кривых и поверхностей.
Наиболее важными инструментами здесь являются параметрические кривые и параметрические поверхности , такие как кривые Безье , сплайновые кривые и поверхности. Важным непараметрическим подходом является метод набора уровней .
Области применения вычислительной геометрии включают судостроение, авиационную и автомобильную промышленность.
Ниже приведен список основных журналов, в которых публикуются исследования в области геометрических алгоритмов. Обратите внимание, что с появлением журналов, специально посвященных вычислительной геометрии, доля геометрических публикаций в журналах общего назначения по информатике и компьютерной графике снизилась.
