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

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

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

Проблемные классы

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

Статические проблемы

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

Выпуклая оболочка : по заданному набору точек найдите наименьший выпуклый многогранник / многоугольник, содержащий все точки.
Пересечение линейных сегментов : найдите пересечения между заданным набором линейных сегментов.
Триангуляция Делоне
Диаграмма Вороного : для заданного набора точек разделите пространство в соответствии с тем, какие точки наиболее близки к данным точкам.
Линейное программирование
Ближайшая пара точек : учитывая набор точек, найдите две, которые находятся на наименьшем расстоянии друг от друга.
Самая дальняя пара точек
Самый большой пустой круг : для данного набора точек найдите самый большой круг с центром внутри их выпуклой оболочки и не охватывающий ни одной из них.
Кратчайший евклидов путь : соедините две точки в евклидовом пространстве (с многогранными препятствиями) кратчайшим путем.
Триангуляция многоугольника: разделите внутреннюю часть многоугольника на треугольники.
Генерация сетки
Логические операции над полигонами

Вычислительная сложность для этого класса задач оценивается временем и пространством (памятью компьютера), необходимыми для решения данного экземпляра проблемы.

Проблемы с геометрическим запросом

В задачах геометрического запроса, обычно известных как задачи геометрического поиска, входные данные состоят из двух частей: части пространства поиска и части запроса , которая варьируется в зависимости от экземпляра задачи. Пространство поиска обычно требует предварительной обработки , чтобы можно было эффективно ответить на несколько запросов.

Вот некоторые фундаментальные проблемы с геометрическими запросами:

Поиск по диапазону : предварительная обработка набора точек для эффективного подсчета количества точек внутри области запроса.
Расположение точки : учитывая разделение пространства на ячейки, создайте структуру данных, которая эффективно сообщает, в какой ячейке находится точка запроса.
Ближайший сосед : предварительная обработка набора точек, чтобы эффективно найти, какая точка является ближайшей к точке запроса.
Трассировка лучей : для заданного набора объектов в космосе создайте структуру данных, которая эффективно сообщает, какой объект луч запроса пересекает первым.

Если пространство поиска фиксировано, вычислительная сложность для этого класса задач обычно оценивается следующим образом:

время и пространство, необходимые для построения структуры данных, в которой будет выполняться поиск
время (а иногда и дополнительное пространство) для ответа на запросы.

В случае, когда разрешено изменять пространство поиска, см. « Динамические проблемы ».

Динамические проблемы

Еще один важный класс - это динамические задачи , цель которых состоит в том, чтобы найти эффективный алгоритм для многократного поиска решения после каждой инкрементальной модификации входных данных (добавления или удаления входных геометрических элементов). Алгоритмы для задач этого типа обычно включают динамические структуры данных . Любая из вычислительных геометрических задач может быть преобразована в динамическую за счет увеличения времени обработки. Например, задача поиска диапазона может быть преобразована в задачу поиска динамического диапазона путем добавления и / или удаления точек. Задача динамической выпуклой оболочки состоит в том, чтобы отслеживать выпуклую оболочку, например, для динамически изменяющегося набора точек, т. Е. Пока входные точки вставляются или удаляются.

Вычислительная сложность для этого класса задач оценивается следующим образом:

время и пространство, необходимые для построения структуры данных, в которой будет выполняться поиск
время и пространство для изменения структуры данных поиска после постепенного изменения в пространстве поиска
время (а иногда и дополнительное пространство) для ответа на запрос.

Вариации

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

Точка в многоугольнике : решите, находится ли точка внутри или за пределами данного многоугольника.

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

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

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

Эта ветвь также известна как геометрическое моделирование и компьютерное геометрическое проектирование (CAGD).

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

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

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

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

использованная литература

^ Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия - Введение . Springer-Verlag . ISBN 0-387-96131-3. 1-е издание; 2-е издание, исправленное и расширенное, 1988 г.
^ А. Р. Форрест, "Вычислительная геометрия", Proc. Лондонское королевское общество , 321, серия 4, 187-195 (1971)
↑ Евгений Б. Карасик (2019). Оптическая вычислительная геометрия . ISBN 979-8511243344.
^ С. Хуллер и Ю. Матиас. Простой алгоритм рандомизированного сита для задачи ближайшей пары . Инф. Вычисл., 118 (1): 34–37,1995 ( PDF )
^ С. Форчун и Дж. Э. Хопкрофт. «Заметка об алгоритме ближайшего соседа Рабина». Письма об обработке информации, 8 (1), стр. 20–23, 1979 г.

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

Список книг по вычислительной геометрии

Журналы

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

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

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

Послушайте эту статью ( 9 минут )

Этот аудиофайл был создан на основе редакции этой статьи от 17 сентября 2013 года и не отражает последующих правок.

[PS-1] Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия - Введение . Springer-Verlag . ISBN 0-387-96131-3. 1-е издание; 2-е издание, исправленное и расширенное, 1988 г.

[2] А. Р. Форрест, "Вычислительная геометрия", Proc. Лондонское королевское общество , 321, серия 4, 187-195 (1971)

[YK-3] Евгений Б. Карасик (2019). Оптическая вычислительная геометрия . ISBN 979-8511243344.

[4] С. Хуллер и Ю. Матиас. Простой алгоритм рандомизированного сита для задачи ближайшей пары . Инф. Вычисл., 118 (1): 34–37,1995 ( PDF )

[5] С. Форчун и Дж. Э. Хопкрофт. «Заметка об алгоритме ближайшего соседа Рабина». Письма об обработке информации, 8 (1), стр. 20–23, 1979 г.

Languages

In other projects