Введение

журнал
Область информатики
Вычислительная геометрия — это область информатики, посвященная изучению алгоритмов, которые могут быть сформулированы в терминах геометрии. Некоторые чисто геометрические задачи возникают в процессе изучения алгоритмов вычислительной геометрии, и эти задачи также считаются частью вычислительной геометрии. Хотя современная вычислительная геометрия — относительно новое направление, это одна из старейших областей вычислений, история которой восходит к античности. Вычислительная сложность играет центральную роль в вычислительной геометрии и имеет большое практическое значение при использовании алгоритмов на очень больших наборах данных, содержащих десятки или сотни миллионов точек. Для таких наборов разница между O(n²) и O(n log n) может означать разницу между днями и секундами вычислений. Основным стимулом для развития вычислительной геометрии как дисциплины был прогресс в компьютерной графике и системах автоматизированного проектирования и производства (CAD/CAM), но многие задачи вычислительной геометрии носят классический характер и могут быть взяты из математической визуализации. Другие важные области применения вычислительной геометрии включают робототехнику (планирование движения и задачи видимости), географические информационные системы (ГИС) (геометрическое определение местоположения и поиск, планирование маршрутов), проектирование интегральных схем (проектирование и верификация геометрии ИС), компьютерную инженерию (CAE) (генерация сеток) и компьютерное зрение (3D-реконструкция). Основные направления вычислительной геометрии:

Комбинаторная вычислительная геометрия, также называемая алгоритмической геометрией, которая рассматривает геометрические объекты как дискретные сущности. Основополагающая книга Препараты и Шамоса датирует первое использование термина «вычислительная геометрия» в этом смысле 1975 годом. Численная вычислительная геометрия, также называемая машинной геометрией, компьютерным геометрическим проектированием (CAGD) или геометрическим моделированием, которая в основном занимается представлением реальных объектов в формах, подходящих для компьютерных вычислений в системах CAD/CAM. Это направление можно рассматривать как дальнейшее развитие описательной геометрии и часто относят к области компьютерной графики или САПР. Термин «вычислительная геометрия» в этом значении используется с 1971 года. Хотя большинство алгоритмов вычислительной геометрии были разработаны (и разрабатываются) для электронных компьютеров, некоторые алгоритмы были разработаны для нетрадиционных компьютеров (например, оптических компьютеров).

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

Основная цель исследований в комбинаторной вычислительной геометрии — разработка эффективных алгоритмов и структур данных для решения задач, сформулированных в терминах основных геометрических объектов: точек, отрезков, многоугольников, полиэдров и т. д. Некоторые из этих задач кажутся настолько простыми, что не рассматривались как задачи до появления компьютеров. Рассмотрим, например, задачу о ближайшей паре:

Дано n точек на плоскости, найдите две точки с минимальным расстоянием между ними. Можно вычислить расстояния между всеми парами точек, которых всего n(n-1)/2, а затем выбрать пару с наименьшим расстоянием. Этот алгоритм полного перебора требует O(n²) времени, то есть время его выполнения пропорционально квадрату числа точек. Классическим результатом в вычислительной геометрии стало создание алгоритма, работающего за O(n log n). Также были разработаны рандомизированные алгоритмы со средним временем работы O(n) и детерминированный алгоритм, работающий за O(n log log n).

Классы проблем

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

Вариации

Некоторые проблемы могут рассматриваться как относящиеся к любой из этих категорий, в зависимости от контекста. Например, рассмотрим следующую задачу: «Точка в многоугольнике» – определить, находится ли точка внутри или снаружи заданного многоугольника. Во многих приложениях эта задача рассматривается как задача единичного выполнения, то есть относящаяся к первому классу. Например, во многих приложениях компьютерной графики распространенной задачей является определение того, в какую область экрана кликнул указатель. Однако в некоторых приложениях рассматриваемый многоугольник остается неизменным, а точка представляет собой запрос. Например, входной многоугольник может представлять границу страны, а точка – положение воздушного судна, и задача состоит в том, чтобы определить, нарушило ли судно границу. Наконец, в ранее упомянутом примере компьютерной графики, в CAD-приложениях изменяющиеся входные данные часто хранятся в динамических структурах данных, которые можно использовать для ускорения запросов «точка в многоугольнике». В некоторых контекстах задач запросов существуют обоснованные ожидания относительно последовательности запросов, которые можно использовать для эффективных структур данных или для более точных оценок вычислительной сложности. Например, в некоторых случаях важно знать наихудший случай для общего времени обработки всей последовательности из N запросов, а не для отдельного запроса. См. также «Амортизированный анализ».

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

Эта отрасль также известна как геометрическое моделирование и автоматизированное геометрическое проектирование (CAGD). Основные задачи – моделирование и представление кривых и поверхностей. Наиболее важными инструментами здесь являются параметрические кривые и параметрические поверхности, такие как кривые Безье, сплайны и поверхности. Важным непараметрическим подходом является метод уровня. Области применения вычислительной геометрии включают судостроение, авиастроение и автомобильную промышленность.