Разработка геометрических алгоритмов: различия между версиями

Базовым этапом многих геометрических алгоритмов является декомпозиция (возможно, сложного) геометрического объекта на более простые подобъекты, каждый из которых обычно имеет константную описательную сложность. Хорошо известным примером является триангуляция многоугольника. Выбор декомпозиции может значительно влиять на практическую эффективность различных алгоритмов, основанных на ней. В пример можно привести сумму Минковского многоугольников на плоскости. Сумма Минковского двух множеств A и B в пространстве <math>\mathbb{R}^d</math> представляет собой векторную сумму двух множеств <math>A \oplus B = \{a + b | a \in A, b \in B \}</math>. Простейший подход вычисления сумм Минковского для двух многоугольников на плоскости содержит три этапа: Выполнить триангуляцию каждого многоугольника, вычислить сумму каждого треугольника одного многоугольника с каждым треугольником второго многоугольника, объединить все подсуммы. Для асимптотических измерений выбор триангуляции (а не альтернативных способов декомпозиции) не имеет определяющего эффекта. Однако на практике триангуляция, вероятно, является худшим вариантом по сравнению с другими выпуклыми декомпозициями, даже относительно простыми эвристическими (не обязательно оптимальными), что подтвердили эксперименты с различными методами декомпозиции [4]. Причина в том, что триангуляция повышает общую сложность подсумм, что, в свою очередь, усложняет этап объединения – на константный коэффициент, однако на практике этот коэффициент сказывается весьма заметно. Аналогичные феномены наблюдались и в других ситуациях. Например, при использовании преимущественно вертикальной декомпозиции расположений она нередко оказывается слишком дорогостоящей по сравнению с более разреженными декомпозициями (т.е. декомпозициями, добавляющими меньше дополнительных функций).

В геометрических вычислениях часто встречается задача обработки заданного планарного подразбиения (плоской карты), которая позволила бы эффективно отвечать на вопросы о местонахождении точек: пусть дана точка q на плоскости; в какой грани карты содержится q? За много лет в рамках проекта CGAL было реализовано множество алгоритмов локализации точки на плоской карте, в частности, иерархическая структура поиска, гарантирующая логарифмическое время выполнения запроса после предварительной обработки карты с n контурами, выполняемой за ожидаемое время O(n log n). Этот алгоритм в библиотеке CGAL носит название алгоритма локализации точек RIC и выполняется после этапа предобработки, использующего рандомизированный алгоритм с пошаговым построением (randomized incremental construction). Кроме того, было реализовано несколько более простых для программирования алгоритмов локализации точек. Однако ни один из них не превосходит RIC по скорости выполнения запросов. Однако с точки зрения предобработки RIC на сегодняшний день является самым медленным из всех реализованных алгоритмов, что во многих сценариях приводит к неэффективности его использования. Один из более простых разработанных методов представляет собой вариант хорошо известного алгоритма прыжков и переходов (jump-and-walk) для локализации точек. Алгоритм разбрасывает по карте точки, так называемые ориентиры, использует их (вместе с содержащими их гранями) в структуре поиска ближайших соседей. После выдачи запроса о точке q алгоритм находит ближайший к q ориентир I и «переходит» по карте из I в q по соединяющему их отрезку прямой. Подход на основе ориентиров обеспечивает лишь ненамного большее время выполнения запроса по сравнению с RIC, зато очень эффективен на этапе предобработки. Его детальное изложение можно найти в работе [10]. Это еще одно соображение, которое необходимо учитывать при проектировании (геометрических) алгоритмов: стоимость предобработки (и хранения) по сравнению со стоимостью выполнения запроса. Нередко эффективный (на практике) компромисс между этими параметрами приходится находить экспериментальным путем.