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

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

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

Основным стимулом для развития вычислительной геометрии как дисциплины был прогресс в компьютерной графике и автоматизированном проектировании и производстве ( CAD / CAM ), но многие проблемы вычислительной геометрии имеют классическую природу и могут исходить из математической визуализации .

Другие важные приложения вычислительной геометрии включают робототехнику ( планирование движения и задачи видимости), географические информационные системы (ГИС) (геометрическое расположение и поиск, планирование маршрута), проектирование интегральных схем (проектирование и проверка геометрии ИС), автоматизированное проектирование (CAE). (создание сетки), компьютерное зрение ( 3D-реконструкция ).

Основные разделы вычислительной геометрии:

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

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

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

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

• Учитывая n точек на плоскости, найдите две точки с наименьшим расстоянием друг от друга.

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

Классы проблем [ править ]

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

Статические проблемы [ править ]

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

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

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

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

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

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

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

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

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

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

Динамические проблемы [ править ]

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

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

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

Варианты [ править ]

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

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

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

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

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

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

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

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

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

См. Также [ править ]

• Список тем комбинаторной вычислительной геометрии
• Список тем по численной вычислительной геометрии
• CAD / CAM / CAE
• Список геометрических алгоритмов
• Твердотельное моделирование
• Вычислительная топология
• Компьютерное представление поверхностей
• Цифровая геометрия
• Дискретная геометрия (комбинаторная геометрия)
• Разделение пространства
• Трехкомплексный номер
• Надежные геометрические вычисления
• Викиверситет: Тема: Вычислительная геометрия
• Викиверситет: компьютерный геометрический дизайн

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

Журналы [ править ]

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

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

• Опросы ACM Computing
• Транзакции ACM на графике
• Acta Informatica
• Достижения в геометрии
• Алгоритмика
• Ars Combinatoria
• Вычислительная геометрия: теория и приложения
• Коммуникации ACM
• Компьютерный геометрический дизайн
• Компьютерная графика и приложения
• Мир компьютерной графики
• Дискретная и вычислительная геометрия
• Геомбинаторика
• Geometriae Dedicata
• Транзакции IEEE для графики
• Транзакции IEEE на компьютерах
• IEEE Transactions по анализу шаблонов и машинному анализу
• Письма об обработке информации
• Международный журнал вычислительной геометрии и приложений
• Журнал комбинаторной теории , серия B
• Журнал вычислительной геометрии
• Журнал дифференциальной геометрии
• Журнал ACM
• Журнал алгоритмов
• Журнал компьютерных и системных наук
• Наука управления
• Распознавание образов
• Письма с распознаванием образов
• SIAM Журнал по вычислениям
• Новости SIGACT ; представил "Столбец вычислительной геометрии" Джозефа О'Рурка
• Теоретическая информатика
• Визуальный компьютер

Внешние ссылки [ править ]

• Вычислительная геометрия
• Страницы вычислительной геометрии
• Геометрия в действии
• "Стратегические направления в вычислительной геометрии - отчет Рабочей группы" (1996)
• Журнал вычислительной геометрии
• (Ежегодная) Зимняя школа по вычислительной геометрии
• Лаборатория вычислительной геометрии

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

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

( Аудио справка  · Больше устных статей )