stringtranslate.com

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

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

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

Основными проблемами являются моделирование и представление кривых и поверхностей.

Наиболее важными инструментами здесь являются параметрические кривые и параметрические поверхности , такие как кривые Безье , сплайновые кривые и поверхности. Важным непараметрическим подходом является метод набора уровней .

Области применения вычислительной геометрии включают судостроение, авиастроение и автомобилестроение.

Список алгоритмов

Смотрите также

Ссылки

  1. ^ Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия - Введение . Springer-Verlag . ISBN 0-387-96131-3. 1-е издание; 2-е издание, исправленное и дополненное, 1988 г.
  2. ^ AR Forrest, "Вычислительная геометрия", Proc. Королевского общества Лондона , 321, серия 4, 187-195 (1971)
  3. ^ Евгений Б. Карасик (2019). Оптическая вычислительная геометрия . ISBN 979-8511243344.
  4. ^ S. Khuller и Y. Matias. Простой рандомизированный алгоритм решета для задачи о ближайших парах. Inf. Comput., 118(1):34—37,1995 ( PDF )
  5. ^ S. Fortune и JE Hopcroft. "Заметка об алгоритме ближайшего соседа Рабина". Information Processing Letters, 8(1), стр. 20—23, 1979

Дальнейшее чтение

Журналы

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

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

Внешние ссылки

Послушайте эту статью ( 9 минут )
Разговорный значок Википедии
Этот аудиофайл был создан на основе редакции этой статьи от 17 сентября 2013 года и не отражает последующие правки. ( 2013-09-17 )