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