Разработка геометрических алгоритмов

Ключевые слова и синонимы

Сертифицированная и эффективная реализация геометрических алгоритмов; геометрические вычисления с сертифицированными численными данными и топологией

Постановка задачи

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

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

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

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

Трудности адаптации на практике существующей обширной алгоритмической литературы по вычислительной геометрии вызваны главным образом предположениями, обычными для теоретических исследований геометрических алгоритмов, которые заключаются в следующем: (1) входные данные находятся в общем положении, а именно, вырожденные входные данные исключены из рассмотрения; (2) вычисление выполняется на идеальном компьютере, поддерживающем операции арифметики действительных чисел с бесконечной точностью (так называемой модели «real RAM»); (3) стоимость операций на небольшом числе простых геометрических объектов соответствует «единичному» времени (например, пересечению трех сфер и сравнению двух целых чисел назначается одинаковая стоимость).

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