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

Базовым этапом многих геометрических алгоритмов является декомпозиция (возможно, сложного) геометрического объекта на более простые подобъекты, каждый из которых обычно имеет константную описательную сложность. Хорошо известным примером является триангуляция многоугольника. Выбор декомпозиции может значительно влиять на практическую эффективность различных алгоритмов, основанных на ней. В пример можно привести сумму Минковского многоугольников на плоскости. Сумма Минковского двух множеств A и B в пространстве Rd представляет собой векторную сумму двух множеств A (В B = fa + bja 2 A; b 2 Bg. Простейший подход вычисления сумм Минковского для двух многоугольников на плоскости содержит три этапа: Выполнить триангуляцию каждого многоугольника, вычислить сумму каждого треугольника одного многоугольника с каждым треугольником второго многоугольника, объединить все подсуммы. Для асимптотических измерений выбор триангуляции (а не альтернативных способов декомпозиции) не имеет определяющего эффекта. Однако на практике триангуляция, вероятно, является худшим вариантом по сравнению с другими выпуклыми декомпозициями, даже относительно простыми эвристическими (не обязательно оптимальными), что подтвердили эксперименты с различными методами декомпозиции [4]. Причина в том, что триангуляция повышает общую сложность подсумм, что, в свою очередь, усложняет этап объединения – на константный коэффициент, однако на практике этот коэффициент сказывается весьма заметно. Аналогичные феномены наблюдались и в других ситуациях. Например, при использовании преимущественно вертикальной декомпозиции расположений она нередко оказывается слишком дорогостоящей по сравнению с более разреженными декомпозициями (т.е. декомпозициями, добавляющими меньше дополнительных функций).