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

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

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

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

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

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

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

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

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

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

Основные результаты

В последние годы были вложены значительные усилия в разработку и реализацию надежных программ вычислительной геометрии. Можно привести в пример два масштабных проекта – библиотеку CGAL [1] и геометрическую составляющую библиотеки LEDA [14]. Они были рассмотрены совместно в обзоре Кеттнер и Наэр [13]. Множество других релевантных проектов рассмотрены в обзоре Джосвига [12], содержащем обширный список ссылок на статьи и веб-сайты.

Приступая к реализации геометрического алгоритма, необходимо принять фундаментальное решение о том, на какой арифметике он будет базироваться, иначе говоря, следует ли рассчитывать на точное вычисление или использовать машинную арифметику с плавающей запятой. Существуют и другие, менее распространенные подходы. На данный момент библиотеки CGAL и LEDA основываются почти исключительно на точных вычислениях. Одна из причин этого выбора заключается в том, что точные вычисления моделируют идеальный компьютер (для ограниченных задач) и тем самым упрощают адаптацию алгоритмов из теоретической формы к программному продукту. Этому способствовал также значительный прогресс в разработке инструментов для эффективных вычислений с рациональными или алгебраическими числами (GMP [3], LEDA [14], CORE [2] и т. д.). На базе этих инструментов были разработаны продуманные техники сокращения объема точных вычислений, такие как фильтры с плавающей запятой и геометрическая фильтрация более высокого уровня.

Альтернативный подход заключается в использовании машинной арифметики с плавающей запятой, обладающей преимуществом высокой скорости. Однако ему далеко до идеальной арифметики с бесконечной точностью, с которой мы имеем дело при теоретическом исследовании геометрических алгоритмов, из-за чего алгоритмы приходится значительно перерабатывать. С рассуждениями по поводу неточности можно ознакомиться, например, в руководстве по QHULL – программе для нахождения выпуклой оболочки Барбера и др. [5]. За много лет было предложено немало специально адаптированных вариантов алгоритмов с плавающей запятой, среди которых, например, тщательно разработанный пакет VRONI авторства Хелда [11], вычисляющий диаграмму Вороного для точек и отрезков прямых при помощи стандартной арифметики с плавающей запятой, основанной на топологически ориентированном подходу Сугихары и Ири. На практике VRONI работает очень хорошо, однако он не является теоретически сертифицированным. Контролируемое возмущение [9] представляет собой последовательный метод получения сертифицированных аппроксимаций сложных геометрических конструктов с применением арифметики с плавающей запятой: Входные данные подвергаются возмущению таким образом, что все предикаты вычисляются точно даже при помощи машинной арифметики с ограниченной точностью, а используемый метод ограничивает необходимую величину возмущения, гарантируя успешное завершение вычисления.

Еще одно решение, которое необходимо принять, касается представления результата выполнения алгоритма; главная проблема обычно заключается в том, как представлять координаты вершин полученных структур. Любопытно, что этот вопрос остается столь же важным и в случае точных вычислений, поскольку могут получиться координаты, недопустимо большие или просто недоступные для конечного перечисления. (Стоит отметить, что многие геометрические алгоритмы являются только селективными – иначе говоря, они не производят новых геометрических объектов, а только выбирают и упорядочивают подмножества координат из входных данных. Например, результатом работы алгоритма вычисления выпуклой оболочки для множества точек является упорядочение подмножества исходных точек. Вычисления новых точек не производится. В данной статье мы обсуждаем главным образом алгоритмы, дающие на выходе новые геометрические конструкции – такие как точка пересечения двух прямых). Но даже при использовании арифметики с плавающей запятой некоторые могут предпочесть более компактное битовое представление чем, например, числа с двойной точностью. В этом направлении существует эффективное, хорошо изученное решение для случая с многоугольниками на плоскости под названием «выравнивание с привязкой» (snap rounding), которое позволяет привязать вершины и точки пересечения к вершинам сетки, сохраняя при этом определенные топологические свойства требуемой точной структуры. Выравнивание с гарантиями в общем случае представляет собой очень сложную задачу, и уже для многогранников в 3-мерном пространстве текущие попытки обобщения алгоритмы выравнивания с привязкой оказываются исключительно дорогостоящими (повышая сложность выравниваемых объектов до третьего и даже более высокого порядка).

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

Декомпозиция