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

На правах рукописи

Дворцов Владислав Игоревич

КОМПЛЕКСНОЕ ИССЛЕДОВАНИЕ И РАЗРАБОТКА

ЭФФЕКТИВНЫХ АЛГОРИТМОВ ТРИАНГУЛЯЦИИ ПРОСТОГО МНОГОУГОЛЬНИКА

Специальность: 05.13.18. - Математическое моделирование,

численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург - 2006

Работа выполнена в Санкт-Петербургском государственном электротехническом университете "ЛЭТИ" им. В. И. Ульянова (Ленина).

Научный руководитель -

кандидат технических наук, доцент Ивановский С. А.

Официальные оппоненты:

доктор технических наук, профессор Постников Е.В. кандидат технических наук, доцент Макулов В. Б.

Ведущая организация - Санкт-Петербургский Морской Технический

Университет.

Защита диссертации состоится «¿^ »¿рвёрАпЛ. 2006 г. ъСО часов на заседании диссертационного совета Д 212.238.01 Санкт-Петербургского государственного электротехнического университета «ЛЭТИ» имени В. И. Ульянова (Ленина) по адресу: 197376, Санкт-Петербург, ул. Проф. Попова, 5.

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан « /3

к----—

Ученый секретарь /

диссертационного совета

Г'

Пантелеев М.Г.

М 33 1

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Вычислительная геометрия (computational geometry) в настоящее время является одной из быстро развивающихся областей компьютерной науки. В значительной степени это связано с научным прогрессом в области компьютерных технологий. Достижения вычислительной геометрии и компьютерной графики используются во многих классах программных систем: в геоинформационных системах (ГИС); системах автоматизированного проектирования (САПР); в системах визуализации, анализа и интерпретации данных и т.п. С ростом мощности вычислительной техники появляется возможность решать задачи, в том числе геометрического характера, все больших и больших размеров. Триангуляции простого многоугольника ( II1М, декомпозиция многоугольника без самопересечений в коллекцию треугольников) как одной из базовых задач вычислительной геометрии уделяется немалое внимание. Множество специалистов по всему миру внесли свой вклад в решение задачи триангуляции, среди них Ф.Препарата, М. Шеймос, Б. Чазелли, Д. Киркпатрик, Д. О'Рурк, Р. Сайдель, Р.Тарьян, Н. Амато, Д. Шевчук, М. Ласло, М. Гудрич, М. Хелд, Д. Рупперт, Т.Сеусл, Д. Добкин, Г. Туссан, К. Конг, А. Фурнье, Д. Монтуно, Д. Инчерпи, С. Скиена, А. С. Скворцов, Ю. JI. Костюк, A. JI. Фукс и многие другие.

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

В России исследования по триангуляции в основном связаны с задачей триангуляции Делоне (т.е. триангуляции заданного множества точек), так как она является базовым блоком в построении геоинформационных систем. Есть хорошие и эффективные алгоритмы триангуляции Делоне и триангуляции Делоне с ограничениями, предложенные А. С. Скворцовым, A. JI. Фуксом, Ю.Л. Костюком. Именно А. С. Скворцов одним йэтгервявнгенельзовал технику кэширования для построения триангуляции Д4лоне^^З^^^##^5)едложил

I. ¿j&fe-'

специальную технику предобработки входных данных, что позволило получить довольно быстрые алгоритмы триангуляции Делоне, имеющие линейную асимптотическую оценку в среднем. Задача ТПМ в работах российских авторов почти не встречается.

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

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

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

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

Задачи исследований.

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

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

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

2) Предложены эффективные и вычислительно устойчивые алгоритмы ТПМ.

На защиту выносятся следующие положения;

1) Последовательный рандомизированный алгоритм ТПМ с использованием кэширования и динамической коррекции.

2) Модификация алгоритма Грэхема с использованием индексирования.

3) Модификация алгоритма Сайделя, основанная на кэшировании трапеций в дереве локализации.

4) Параллельный алгоритм построения псевдотриангуляции простого многоугольника.

Практическая ценность.

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

Внедрение результатов работы:

Работа выполнялась в рамках НИР «Интеллектуализация методов решения задач предстартовой подготовки и обработки телеметрической и внешнетраекторной информации применительно к анализу параметров полета объектов РКТ» (раздел: применение методов когнитивной графики в задачах обработки), а также в ОКР, связанных с визуализацией данных при решении задач сбора, оперативного отображения и обработки измерений в реальном масштабе времени и в послесеансном режиме в сложных научно-технических комплексах, проводимых в ОАО "Научно-инженерный центр электротехнического университета"

Разработанные программные средства и методические материалы использовались в учебном процессе при проведении лабораторных и курсовых работ по курсу «Комбинаторные алгоритмы вычислительной геометрии» для студентов СПбГЭТУ специальности «Прикладная математика» и для студентов, обучающихся в магистратуре по направлениям «Прикладная математика и информатика» и «Информатика и вычислительная техника».

Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на научно-технических конференциях СПбГЭТУ в 2004-2005 гг.; на 7-ой международной конференции

«Распознавание образов и анализ изображений» (РОАИ-7 2004), Санкт-Петербург 2004; на II Международной конференции «Автоматизация, управление и информационные технологии-2005» (АСГГ2005) Новосибирск; на XV Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании» Пенза 2005; на конкурс-конференции студентов и молодых ученых Северо-запада 2004 в СПбГПУ (работа заняла первое место); на конкурс-конференции студентов и молодых ученых Северо-запада 2005 в СПбГПУ; на одиннадцатой ежегодной международной научно-технической конференции студентов и аспирантов «Прикладная математика» Москва 2005.

Публикации. По теме диссертации опубликовано 11 научных работ, из них — 7 статей и 4 работы в материалах международных и всероссийских научно-технических конференций.

Структура и объем диссертации. Диссертация состоит из введения, шести глав, заключения и списка литературы, включающего 75 наименований. Основная часть работы изложена на 123 страницах машинописного текста. Работа содержит 62 рисунка и 11 таблиц.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении показана и обоснована актуальность работы, сформулированы основные цели и задачи, научная новизна и практическая ценность работы.

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

Задача триангуляции формулируется следующим образом «даны координаты п вершин простого многоугольника Р в порядке его обхода, необходимо найти и-3 не пересекающихся диагоналей, которые делят Р на п-2 треугольника».

На рис. 1 приведен пример построенной ТПМ при п =50.

Рис.1. Триангуляция простого многоугольника

Долгое время нетривиальная нижняя граница сложности задачи ТПМ оставалась неизвестной. В 1990 году Б. Чазелли предложил детерминированный алгоритм с линейной асимптотической оценкой и показал, что это оптимальный результат. Однако среди специалистов по вычислительной геометрии сложилось мнение о том, что алгоритм Чазелли представляет собой лишь доказательную схему для получения оценки, и он безнадежен для практической реализации. В большинстве известных алгоритмов с хорошими асимптотическими оценками, как правило, прямая } задача триангуляции простого многоугольника не решается, а рассматривается

двойственная ей задача трапецеидальной декомпозиции (построение , горизонтальной карты видимости для множества ребер и вершин

многоугольника). За последние десятилетие сформировалось мнение, что практически оптимальным является рандомизированный алгоритм, предложенный Р. Сайделем, с асимптотической оценкой - О(п1о^'п). Возможность практической реализации предложенного Н. Амато, М. Гудричем и Э. Рамос (АГР) рандомизированного алгоритма ТПМ, имеющего 0(п) оценку в среднем и являющегося комбинацией идей Р. Сайделя и Б. Чазелли, остается неясной. С практической точки зрения можно считать, что, несмотря на наличие теоретически привлекательных алгоритмов, задача построения ТПМ с помощью эффективного алгоритма не является полностью решенной. В частности, она все еще остается в списке открытых проблем вычислительной геометрии.

Рис. 2. Классификация алгоритмов ТПМ

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

реализации. В частности, подробно описан алгоритм АГР, с акцентом на реализацию, так как такого описания нет ни в одном источнике. Выявлены основные достоинства и проанализированы недостатки каждого алгоритма ТПМ.

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

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

V' -Ч5| ¡¡й*

Ж*

У? Щ & § •

«9» •

•Д да» к«: «А

• •

а # , •

• ■

Рис. 3.

Описана структура данных для представления триангуляции простого многоугольника, которая хранит информацию о соседних треугольниках, ребрах и вершинах.

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

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

На базе предложенной методики кэширования для локализации точки в триангуляции предложены несколько алгоритмов:

- последовательная триангуляция с использованием кэширования и динамической коррекции текущей триангуляции;

- триангуляция методом кэширования (ТМК);

( - трапецеидальная декомпозиция Сайделя с кэшированием;

- триангуляция с кэшированием и предобработкой;

- псевдотриангуляция с кэшированием и параллельной обработкой.

Основной принцип алгоритма последовательной триангуляции с

использованием кэширования и динамической коррекции текущей

триангуляции можно описать следующим образом:

BEGIN

1 Тг(0) = охватывающий четырехугольник;

2 Добавить в Тг(0) точку р(0), чтобы получить Тг(1); на выходе четыре

треугольника

3 FOR i:=l ТО k DO

4 R[i]:~ ссылка на треугольник, которому принадлежит ячейка;

5 FOR i:=l TOnDO

6 BEGIN

7 Локализация p(i) в Tr(i-l) // Tr(i-l). triangle - локализованный

треугольник;

8 R[i]p — ссылка на Tr(i-l). triangle;

9 Добавить в Tr(i-1), точку p(i), чтобы получить Tr(i);

10 Добавить в Tr(i), pe6po(p(i-l),p(i));

11 END;

12 Clear(P, Tr(n)); Удалить все ребра вне триангуляции многоугольника

END.

Здесь Tr(i) - структура для представления текущей триангуляции для цепи (р(1) ..p(i)); p(i) для i=l..n - вершины простого многоугольника; R - кэш, размером yfkx^fk.

Идея алгоритма ТМК заключается в построении триангуляции множества точек с использованием кэширования и лишь после этого добавления всех i> ребер многоугольника для получения ТПМ. Именно он является базой для

алгоритма последовательной триангуляции с использованием кэширования и динамической коррекции.

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

Алгоритм ТПМ с предобработкой строит древовидную структуру, в которой определяется порядок добавления вершин в триангуляцию, и использует этот порядок при выборе очередной вершины для построения триангуляции вместо рандомизации.

В параллельном алгоритме ТПМ с использованием кэширования вводится понятия псевдотриангуляции и применяется полосовое разбиение многоугольника с построением триангуляции в каждой полосе.

Выполнен асимптотический анализ алгоритмов для среднего и худшего случая (таб.1) (к - количество вогнутых вершин в многоугольнике).

Таблица 1

ирценка« ____вМННкЯ£ГЭП№к

ч . J -_ ' "I *

■н&и

Сканирование Грэхема с индексированием 0(пк) 0(п2)

Триангуляция методом кэширования (ТМК) О(п) 0(п2)

Триангуляция методом кэширования и динамической коррекции 0{п) 0(п2)

Трапецеидальная декомпозиция Сайделя с кэшированием 0(и1о§ п) 0{п п)

Триангуляция с предобработкой 0(п) 0(и2)

Псевдотриангуляция 0{п) 0(п п)

В третьей главе рассматривается вспомогательная задача, которая возникает при необходимости комплексного исследования и сравнительного анализа алгоритмов, а именно: генерация представительного (разных типов и размеров) класса простых многоугольников. В общем случае эта задача сложнее задачи ТПМ и имеет нижнюю границу £2(и1о§и).

200 вершин

200 вершин

500 вершин 1000 вершин

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

многоугольников. Примеры различных типов простых многоугольников с разным количеством вершин на рисунке 5.

Приводится асимптотический анализ каждого из алгоритмов для худшего случая (таб. 2)._

п Методом сортировки 0(п п)

2 Методом полярной сортировки 0{п\о%п)

3 Методом разделения пространства 0{пг)

Т Методом последовательной вставки 0(п2 10£Л)

Т Метод триангуляции Делоне 0(п п)

В четвертой главе подробно описаны проблемы вычислительной устойчивости алгоритмов триангуляции и генерации простого многоугольника и методы их решения.

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

В таблице 3 представлен эмпирический анализ вычислительной устойчивости алгоритмов триангуляции и генерации простого многоугольника в зависимости от количества вершин. Звездочкой отмечена вычислительная неустойчивость алгоритма на данном размере задачи.

Таблица 3

МШюР. МИ1

10 ООО ; 20 ООО 50 000 100 000'

Триангуляция многоугольника

Декомпозиция на монотонные многоугольники - * * *

Расщепление вдоль хорды - * * *

Сканирование Грэхема - * * *

Трапецеидальная декомпозиция Сайделя - - + *

Трапецеидальная декомпозиция АГР - * * ♦

Сканирование Грэхема с индексированием - - - *

Триангуляция методом кэширования - - * *

Триангуляция методом кэширования и динамической коррекции - - * *

Трапецеидальная декомпозиция Сайделя с кэшированием - * *

Триангуляция с предобработкой _ * ♦

Псевдотриангуляции - * ♦

Генерация многоугольника

Методом сортировки - - - -

Методом полярной сортировки - - - -

Методом разделения пространства - - * *

Методом последовательной вставки - * * *

Метод триангуляции Делоне - - * *

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

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

Экспериментально установлено, что при применении адаптивных алгоритмов с вещественной арифметикой время работы алгоритмов в худшем случаи увеличивается на 30%, хотя этот худший случай достигается только в алгоритме АГР, а в среднем это увеличение времени составляет всего 15%.

В пятой главе даны оценки сложности реализации каждого из алгоритмов и основные сведения о реализации и подготовке исследования.

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

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

При проведении тестирования и исследования алгоритмов результаты генерации простых многоугольников подвергались проверке на простоту (отсутствие самопересечений), а результаты алгоритмов ТПМ подвергались проверке на правильность построенной структуры (правильное количество диагоналей и отсутствие самопересечений). Приведен принцип основных проверок.

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

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

Реализация осуществлялась с использованием среды УС++, технологии объектно-ориентированного программирования. Оптимизированный код базовых алгоритмов написан на языке С.

В таблице 4 приведена оценка сложности реализации по пятибалльной шкале и время выполнения каждого из алгоритмов при заданном простом многоугольнике из 100 ООО вершин, построенном методом разделения пространства. Под сложностью реализации понимается совокупность таких показателей как количество дополнительных условий, которые нужно учесть при программной реализации, и трудоемкость самого процесса программирования.

Таблица 4

птмп -

Декомпозиция на монотонные многоугольники *** 84,4

Расщепление вдоль хорды ** 133,7

Сканирование Грэхема ** 221,5

Трапецеидальная декомпозиция Сайделя **** 90,1

Трапецеидальная декомпозиция АГР ***** 338,4

Сканирование Грэхема с индексированием *** 120,7

Триангуляция методом кэширования **** 28,8

Триангуляция методом кэширования и динамической коррекции **** 24,6

Трапецеидальная декомпозиция Сайделя с кэшированием ***** 78,1

Триангуляция с предобработкой **** 182,4

Псевдотриангуляция **** 118,5

В шестой главе проводится сравнительный анализ реализованных (известных и предложенных) алгоритмов ТПМ на простых многоугольниках различных размеров и типов. Показывается, что при сравнении алгоритмов для анализа достаточно рассматривать многоугольники с 100 000 вершинами, так как далее при увеличении количества вершин поведение алгоритмов становится стабильным.

При небольшом размере простого многоугольника (порядка 10 000 вершин) наилучшие результаты для большинства типов многоугольников достигнуты предложенным модифицированным алгоритмом сканирования Грэхема с индексированием. Уже при этом количестве вершин время работы модификаций алгоритмов меньше, чем у известных алгоритмов. Выявлено, что алгоритм триангуляция методом кэширования с динамической коррекцией

кэширования. Алгортш методом много„голшмах и

КГ™"«—«ТдоГГр^имеГменьмее .рем, „а _ м»»^—последовательного алгоритма

эт0 м—Тс^ля, то о„ весьма

-ООО

известные квадратичные алгоритмы по пР™ резког У^ по той

построения, а также ^^^

:;ГИрХаГ на рисунке 6 представлена

соответственно таблице 2.

Рис 6 Поведения алгоритмов на многоугольниках разных типов

Вое! Работы А™ триангуляции с предобработкой на равномерном приие больше чем у алгоритмов с кэшированием и рандомизациеи. распредел^ие^болш^ч^^У^ построения

на параллельной структуре. Моделировалась параллельная обработка на одном

процессоре (в восьми полосах). В качестве времени работы алгоритма брался шах^ Г,, где Г, - время построения алгоритма на одном процессоре (в одной

полосе). В таблице 5 представлены результаты анализа времени выполнения в зависимости от количества вершин в многоугольнике (ТМК - временная оценка алгоритма триангуляции методом кэширования при тех же условиях).

Таблица 5.

10 000 50 000 100 000

8 к= 1 7,104 48,236 118,5

тах Т, 1 = 1..8 1,065 7,265 14,913

ТМК 4,087 16,348 28,8

К. 2 з,з з,з

Таким образом, при замене задачи ТПМ на задачу с псевдотриангуляцией в несколько раз увеличивается количество вершин триангуляции (эмпирически

установлено, что коэффициент увеличения - ), но если есть возможность распараллеливания, то при этом достигается выигрыш вд времени.

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

Итак, получены следующие результаты при сравнительном анализе алгоритмов:

- предложенные алгоритмы ТПМ работают быстрее, чем известные алгоритмы триангуляции;

- использование кэширования и индексирования при построении ТПМ дает значительный выигрыш;

- использование адаптивной вещественной арифметики позволяет сделать алгоритмы триангуляции и генерации простого многоугольника вычислительно устойчивыми к различным входным данным, при этом временные потери не превышают тридцати процентов, а во многих случаях ограничиваются 15%;

- использование алгоритмов с хорошими асимптотическими оценками в среднем целесообразно и практически оправдано (время построения меньше, чем у других);

- в зависимости от топологического класса входных многоугольников и размера входных данных есть смысл использовать различные алгоритмы ТПМ, в том числе имеющие не лучшие асимптотические оценки, чем другие;

существенная эффективность достигается использованием рандомизацией входных данных (например, в алгоритмах с кэшированием);

- предложенный параллельный алгоритм псевдо триангуляции показал хорошие результаты при моделировании и при возможности распараллеливать задачу триангуляции целесообразно его использование;

- алгоритм триангуляции с предобработкой хотя и работает быстрее многих алгоритмов, но уступает лучшим из них при равномерном распределении, а при неравномерном распределении показывает наилучшие характеристики;

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

ЗАКЛЮЧЕНИЕ

Основные научные и практические результаты работы можно сформулировать следующим образом:

1) Предложен последовательный рандомизированный алгоритм ТПМ с использованием кэширования и динамической коррекции, который имеет наилучшие временные показатели среди всех исследованных алгоритмов.

2) Предложена модификация алгоритма Грэхема с использованием индексирования, которая на не очень больших размерах многоугольника (до 20 ООО вершин) имеет наилучшие временные показатели.

3) Предложена модификация алгоритма Сайде ля, основанная на кэшировании трапеций в дереве локализации, улучшающая производительность оригинального алгоритма на многоугольниках до 50 ООО вершин.

4) Предложен алгоритм с предобработкой, основанный на построение специального порядка добавления вершин в текущую триангуляцию, который работает быстрее на неравномерном распределении вершин.

5) Предложен параллельный алгоритм построения псевдотриангуляции простого многоугольника.

6) Предложены алгоритмы генерации простых многоугольников, которые позволяют генерировать представительный класс простых многоугольников.

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

8) Разработаны вычислительно устойчивые алгоритмы с использованием адаптивной вещественной арифметики, корректно работающие на различных многоугольниках с большим количеством вершин.

Публикации по теме диссертации:

1 • Дворцов В. И., Ивановский С. А. Сравнительный анализ алгоритмов триангуляции простого многоугольника. // Изв. СПбГЭТУ «ЛЭТИ». Сер. «Информатика, управление и компьютерные технологии». 2002. Вып. 3. С. 69-73.

2. Дворцов В.И., Ивановский С.А. Эффективный алгоритм триангуляции простого многоугольника // Изв. СПбГЭТУ «ЛЭТИ». Сер. «Информатика, управление и компьютерные технологии». 2004. Вып. 2. С. 52-56.

3. Дворцов В.И., Ивановский С.А. Исследование эффективности рандомизированных алгоритмов триангуляции простого многоугольника // Изд-во СПбГПУ. Материалы межвузовского конкурса-конференции студентов и молодых ученых Северо-Запада. 2004. С. 136-137.

4. Дворцов В.И., Ивановский С.А. Линейные и почти линейные по сложности алгоритмы триангуляции простого многоугольника // 7-ая международная конференция по распознаванию образов и анализу изображений, 2004, том 2, С. 456-459.

5. Дворцов В.И., Ивановский С.А. Линейный параллельный алгоритм для построения псевдотриангуляции простого многоугольника // Одиннадцатая ежегодная международная научно-техническая конференция студентов и аспирантов. Москва. 2005. Том 1. С. 333-334.

6. Дворцов В.И., Ивановский С.А. Вычислительная устойчивость алгоритмов триангуляции простого многоугольника // Изд-во СПбГПУ. Материалы межвузовского конкурса-конференции студентов и молодых ученых Северо-Запада. 2005. С. 163.

7. Дворцов В.И., Ивановский С.А. Адаптивный вычислительно устойчивый эффективный алгоритм триангуляции простого многоугольника // Изд-во СПбГПУ. Материалы межвузовского конкурса-конференции студентов и молодых ученых Северо-Запада. 2005. С. 163164.

8. Дворцов В.И., Ивановский С.А. Linear and almost linear triangulation algorithme for simple polygons (Линейные и почти линейные по сложности алгоритмы триангуляции простого многоугольника) // Pattern Récognition and Image Analysis: Advances in Mathematical Theory and Applications (Изд. МАИК HayKa/Interperiodica Publishing). 2005. P. 379-381.

9. Дворцов В.И., Ивановский С.А. Effective, computational stability parallel algorithm for construction of a pseudo-triangulation of a simple polygon (Эффективный, вычислительно-устойчивый параллельный алгоритм для построения псевдотриангуляции простого многоугольника) // Proceedings of the second IASTED International Multi-Conference Software Engineering (ACIT-SE) (Изд. ACTA Press ISBN: 0-88986-504-3) 2005. P. 108-110.

10. Дворцов В.И., Ивановский C.A., Преображенский A.C. Триангуляция простого многоугольника методом кэширования в трапецеидальной декомпозиции // Известия СПбГЭТУ «ЛЭТИ». Серия «Информатика, управление и компьютерные технологии». 2005. Вып. 2. С. 14-19.

11. Дворцов В.И., Ивановский С.А. Алгоритм триангуляции простого многоугольника с предобработкой // Изд. Пенза. Сборник статей XV Международной научно-технической конференции «Математические методы и информационные технологии в экономике, социологии и образовании» 2005. С. 294-297.

Подписано в печать 26.12.05. Формат 60*84 1/16. Бумага офсетная. Печать офсетная. Печ. л. 1,75. Тираж 100 экз. Заказ 132.

Отпечатано с готового оригинал-макета в типографии Издательства СПбГЭТУ "ЛЭТИ"

Издательство СПбГЭТУ "ЛЭТИ" 197376, С.-Петербург, ул. Проф. Попова, 5

ZOÖGk

аъз

Введение.

1 Триангуляция простого многоугольника: аналитический обзор.

1.1 Триангуляция простого многоугольника.

1.2 Известные алгоритмы триангуляции простого многоугольника.

1.2.1 Алгоритм декомпозиции на монотонные многоугольники.

1.2.2 Алгоритм триангуляции простого многоугольника методом расщепления вдоль хорды.

1.2.3 Алгоритм триангуляции простого многоугольника методом сканирования Грэхема.

1.2.4 Алгоритм трапецеидальной декомпозиции Тарьяна.

1.2.5 Алгоритм трапецеидальной декомпозиции Киркпатрика.

1.2.6 Алгоритм трапецеидальной декомпозиции Сайделя.

1.2.7 Алгоритм трапецеидальной декомпозиции Чазелли.

1.2.8 Алгоритм трапецеидальной декомпозиции АГР.

1.2.9 Двойственность задач триангуляции простого многоугольника и построения трапецеидальной декомпозиции.

1.2.10 Выводы.

2 Предложенные алгоритмы триангуляции простого многоугольника.

2.1 Классификация алгоритмов триангуляции простого многоугольника.

2.2 Индексирование и кэширование.

2.2.1 Модификация алгоритма Грэхема с использованием индексирования.

2.2.2 Рандомизированный алгоритм триангуляции простого многоугольника с использованием кэширования.

2.2.3 Последовательный рандомизированный алгоритм триангуляции простого многоугольника с использованием кэширования и динамической коррекции.

2.2.4 Алгоритм трапецеидальной декомпозиции Сайделя с использованием кэширования.

2.2.5 Алгоритм триангуляции простого многоугольника с предобработкой.

2.2.6 Параллельный алгоритм псевдотриангуляции простого многоугольника.

2.3 Выводы.

3 Генерация простых многоугольников.

3.1 Задача построения простого многоугольника.

3.2 Алгоритмы генерации простого многоугольника.

3.2.1 Алгоритм построения монотонных и немонотонных простых многоугольников методом сортировки.

3.2.2 Алгоритм построения простых многоугольников методом полярной сортировки.

3.2.3 Алгоритм построения простого многоугольника методом разделения пространства.

3.2.4 Алгоритм построения простого многоугольника методом последовательной вставки.

3.2.5 Алгоритм построения простого многоугольника методом триангуляции Делоне.

3.3 Примеры построенных простых многоугольников.

3.4 Выводы.

4 Вычислительная устойчивость алгоритмов триангуляции и генерации простого многоугольника.

4.1 Причины возникновения ошибок при вычислениях.

4.2 Применение целочисленной арифметики.

4.3 Применение адаптивных операций вычисления.

4.4 Поведение алгоритмов при применении вычислительно устойчивых схем.

4.5 Выводы.

5 Реализация и экспериментальное исследование алгоритмов.

5.1 Проверка правильности построенных результатов.

5.2 Основа экспериментального исследования.

6 Сравнительный анализ алгоритмов триангуляции и генерации простого многоугольника.

6.1 Сравнительный анализ алгоритмов генерации простого многоугольника.

6.2 Сравнительный анализ алгоритмов триангуляции простых многоугольников.

Вычислительная геометрия (computational geometry) в настоящее время является одной из быстро развивающихся областей компьютерной науки. В значительной степени это связано с научным прогрессом в области компьютерных технологий. Достижения вычислительной геометрии и компьютерной графики используются во многих классах программных систем: в геоинформационных системах (ГИС); системах автоматизированного проектирования (САПР); в системах интерпретации данных; в системах визуализации и анализа данных и т.п. С ростом мощности вычислительной техники появляется возможность решать задачи, в том числе геометрического характера, все больших и больших размеров. Триангуляции простого многоугольника (ТПМ, декомпозиция многоугольника без самопересечений в коллекцию треугольников) как одной из базовых задач вычислительной геометрии уделяется немалое внимание. Множество специалистов по всему миру внесли свой вклад в решение задачи триангуляции, среди них Ф. Препарата, М. Шеймос, Б. Чазелли, Д. Киркпатрик, Д. О'Рурк, Р. Сайдель, Р. Тарьян, Н. Амато, Д. Шевчук, М. Ласло, М. Гудрич, М. Хелд, Д. Рупперт, Т. Сеусл, Д. Добкин, Г. Туссан, К. Конг, А. Фурнье, Д. Монтуно, Д. Инчерпи, С. Скиена, А. С. Скворцов, Ю. J1. Костюк, A. J1. Фукс и многие другие.

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

В России исследования в основном связаны с задачей триангуляции Делоне (т.е. триангуляции заданного множества точек), так как она является базовым блоком в построении геоинформационных систем. Есть хорошие и эффективные алгоритмы триангуляции Делоне и триангуляции Делоне с ограничениями, предложенные А. С. Скворцовым, A. J1. Фуксом, Ю.Л. Костюком. Именно А. С. Скворцов одним из первых использовал технику кэширования для построения триангуляции Делоне, a A. J1. Фукс предложил специальную технику предобработки входных данных, что позволило получить довольно быстрые алгоритмы триангуляции Делоне, имеющие линейную асимптотическую оценку в среднем. Задача ТПМ в работах российских авторов почти не встречается.

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

Одна из основных проблем связана с вычислительной устойчивостью алгоритмов. Алгоритмы ТПМ оперируют с вещественными координатами. Однако в силу особенностей реальных вещественных операций в компьютерах почти всегда существует возможность некорректной работы алгоритмов. При современных объемах обрабатываемых данных такая вероятность очень велика. Именно поэтому в последние годы все большее внимание уделяется созданию вычислительно устойчивых (робастных) алгоритмов.

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

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

Задачи работы

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

Методы исследования

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

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

Предложены эффективные и вычислительно устойчивые алгоритмы

ТПМ.

Практическая ценность

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

Положения, выносимые на защиту

1 Предложен последовательный рандомизированный алгоритм ТПМ с использованием кэширования и динамической коррекции, который имеет наилучшие временные показатели среди всех исследованных алгоритмов.

2 Предложена модификация алгоритма Грэхема с использованием индексирования, которая на не очень больших размерах многоугольника (до 20 ООО вершин) имеет наилучшие временные показатели.

3 Предложена модификация алгоритма Сайделя, основанная на кэшировании трапеций в дереве локализации, улучшающая производительность оригинального алгоритма.

4 Предложен параллельный алгоритм построения псевдотриангуляции простого многоугольника

5 Предложены алгоритмы генерации простых многоугольников, которые позволяют генерировать представительный класс простых многоугольников.

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

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

По теме диссертации опубликовано 11 научных работ, из них - 7 статей и 4 работы в материалах международных и всероссийских научно-технических конференций.

Структура диссертации

Работа состоит из введения, 6 глав, заключения, списка литературы и приложений.

В первой главе формулируется задача триангуляции, проводится аналитический обзор алгоритмов и методов решения задачи.

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

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

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

В пятой главе описываются особенности реализации и постановки экспериментального исследования.

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

Выводы по главам подробно представлены в работе. В данном разделе представлены общие выводы по работе и перспективы использования результатов.

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

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

7. ЗАКЛЮЧЕНИЕ

1. Вирт Н. Алгоритмы + структуры данных = программы / Пер. с англ. М.: Мир, 1985.-406 с.

2. Дворцов В. И., Ивановский С. А. Сравнительный анализ алгоритмов триангуляции простого многоугольника. // Изв. СПбГЭТУ «ЛЭТИ». Сер. «Информатика, управление и компьютерные технологии». 2002. Выпуск 3. с. 69-73.

3. Дворцов В.И., Ивановский С.А. «Эффективный алгоритм триангуляции простого многоугольника» // Известия СПбГЭТУ «ЛЭТИ». Серия «Информатика, управление и компьютерные технологии». 2004. Выпуск 2. с. 52-56.

4. Дворцов В.И., Ивановский С.А. «Вычислительная устойчивость алгоритмов триангуляции простого многоугольника» // Изд-во СПбГПУ. Материалы межвузовского конкурса-конференции студентов и молодых ученых Северо-Запада. 2005. стр. 163.

5. Дворцов В.И., Ивановский С.А. «Адаптивный вычислительно устойчивый эффективный алгоритм триангуляции простого многоугольника» // Изд-во СПбГПУ. Материалы межвузовского конкурса-конференции студентов и молодых ученых Северо-Запада. 2005. стр. 163-164.

6. Канн П. Введение в линейную алгебру М: Мир 1968 - 489с.

7. Кнут Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. М.: Мир, 1976. - 736 с.

8. Кнут Д. Искусство программирования для ЭВМ. Т.2. Получисленные алгоритмы. М.: Мир, 1977. - 724 с.

9. Кнут Д. Искусство программирования для ЭВМ. Т.З. Сортировка и поиск. -М.: Мир, 1978.-844 с.

10. Костюк Ю.Л. Графический поиск с использованием триангуляции и клеточного разбиения // Вестник Томского гос. ун-та, 2002, Т. 273, апрель, с. 147-152.

11. Костюк Ю.Л., Фукс А.Л. Приближенное вычисление оптимальной триангуляции // Геоинформатика. Теория и практика. Вып. 1. Томск: Изд-во Том.ун-та, 1998, с. 61-66.

12. Ласло М. Вычислительная геометрия и компьютерная графика на С++. -М.: БИНОМ, 1997.

13. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. М.: МИР, 1989.

14. Роджерс Д., Адаме Дж. Математические основы машинной графики. Пер. с англ. М.: Машиностроение, 1980. - 204 с.

15. Скворцов А. В. Комплексное исследование и разработка эффективных вычислительно устойчивых алгоритмов вычислительной геометрии и их реализация в геоинформационной системе. //Диссертации на соискание ученой степени д.т.н. Томск 2002 г.

16. Скворцов А.В. Триангуляция Делоне и её применение. Томск: Изд-во Томск, ун-та, 2002. - 128 с.

17. Скворцов А.В. Построение триангуляции Делоне за линейное время // Изв. вузов. Физика, 1999, №3, с. 120-126.

18. Скворцов А.В. Особенности реализации алгоритмов построения триангуляции Делоне с ограничениями // Вестник Томского гос. ун-та, 2002, Т. 273,апрель, с. 90-94.

19. Скворцов А.В., Костюк Ю.Л. Эффективные алгоритмы построения триангуляции Делоне // Геоинформатика: Теория и практика. Выпуск 1. -Томск: Изд-во Томск, ун-та, 1998, с. 22-47.

20. Скворцов А.В., Костюк Ю.Л. Применение триангуляции для решения задач вычислительной геометрии // Геоинформатика: Теория и практика. Выпуск 1. Томск: Изд-во Томск, ун-та, 1998, с. 127-138.

21. Скворцов А.В., Костюк Ю.Л. Сравнительный анализ алгоритмов построения триангуляции Делоне // SCOR-98 (материалы международной конференции). Новосибирск, 1998, с. 138.

22. Уилсон Р. Введение в теорию графов / Пер. с англ. М.: Мир, 1977. - 207с.

23. Фукс. А.Л. Быстрый алгоритм триангуляции Делоне, основанный на предварительной обработке набора точек // Теория геониформатики и дистанционного зондирования, Томск 2002, стр. 45-50.

24. Р. К. Agarwal and Kasturi R. Varadarajan. E±cient algorithms for approximating polygonal chains. Discrete Comput. Geom., 23:273-291, 2000.

25. P. K. Agarwal, B. Aronov, Т. M. Chan, and M. Sharir. On levels in arrangements of lines, segments, planes, and triangles. Discrete Comput. Geom., 19:315-331, 1998.

26. Oswin Aichholzer, Franz Aurenhammer, and Hannes Krasser. On compatible triangulations of point sets. In Abstracts 17th European Workshop Comput. Geom., pages 23-26. Freie Universitat Berlin, 2001.

27. Oswin Aichholzer, Franz Aurenhammer, Hannes Krasser, and Bettina Speckmann. Convexity minimizes pseudo-triangulations. In Proc. 14th Canad. Conf. Comput. Geom., pages 158-161, 2002.

28. N. M. Amato, M. T. Goodrich, and E. A. Ramos. Linear-time triangulation of a simple polygon made easier via randomization. In Proc. 16lh Annu. ACM Sympos. Comput. Geom., 201-212, 2000.

29. Tomas Auer and Martin Held, RPG Heuristics for the Generation of Random Polygons. In Proc. 8th Canad. Conf. Comput. Geom., pages 38-44 ,1996

30. Gerth Brodal and Riko Jacob. Dynamic planar convex hull. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, November 2002.

31. Gerth Brodal and Riko Jacob. Dynamic planar convex hull with optimal query time and o(log n . log log n) update time. In Proc. 7th Scand. Workshop

32. Algorithm Theory, volume 1851 of Lecture Notes Comput. Sci., pages 57-70. Springer-Verlag, 2000.

33. W. S. Chan and F. Chin. Approximation of polygonal curves with minimum number of line segments or minimum error. Internat. J.Comput. Geom. Appl., 6:59-77, 1996.

34. B. Chazelle. Triangulating a simple polygon in linear time. Discrete Comput. Geom., 6(5):485-524, 1991.

35. Chazelle, В., Incerpi, J. Triangulation and shape complexity ACM Trans. On Graphics 3 (1984), 135-152

36. Siu-Wing Cheng and Kam-Hing Lee. Quadtree decomposition, Steiner triangulation, and ray shooting. In ISAAC: 9th Internat. Sympos. Algorithms Computation, pages 367-376, 1998.

37. Matthew T. Dickerson, Scott A. McElfresh, and Mark H. Montague. New algorithms and empirical .ndings on minimum weight triangulation heuristics. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages 238-247, 1995.

38. M. E. Dyer. Linear time algorithms for two- and three-variable linear programs. SIAM J. Comput., 13: 31-45, 1984.

39. Fournier, A., Montuno, D.Y. Triangulating simple polygons and equivalent problems, ACM Trans. On Graphics 3 (1984), 153-174

40. H. de Fraysseix, J. Pach, and R. Pollack. How to draw a planar graph on a grid. Combinatorica, 10(1):41-51, 1990.

41. Garey M.R., Johnson D.S., Preparata F.P., Tarjan R.E. Triangulating a simple polygon II Inform. Process. Left. 1978. №7. pp. 175-180.

42. A. Gajentaan and M. H. Overmars. On a class of 0(n2) problems in computational geometry. Comput. Geom. Theory Appl., 5:165-185, 1995.

43. John Hershberger and Subhash Suri. An optimal algorithm for Euclidean shortest paths in the plane. SIAM J. Comput., 28(6):2215-2256, 1999.

44. J. Hershberger and J. Snoeyink. An 0(n log n) implementation of the Douglas-Peucker algorithm for line simpli.cation. In Proc. 10th Annu. ACM Sympos. Comput. Geom., pages 383-384, 1994.

45. David G. Kirckpatrick, Maria M.Klawe, Robert E. Tarjan, Polygon Triangulation in 0(nloglogn ) time with simple data structures, ACM, 34-43, 1990

46. Kirkpatrik D.G. Optimal search in planar subdivisions // SIAM J. Comput., 1983, Vol. 12, No. l,pp. 28-35.

47. Vladlen Koltun. Almost tight upper bounds for vertical decompositions in four dimensions. In Proc. 42nd Annu. IEEE Sympos. Found. Comput. Sci., 2001.

48. Kong X., Everett H. and Toussaint G. The Graham Scan Triangulates Simple Polygons //Pattern Recognition Letters, 1990 Volume 11, p. 713-716

49. Lee D.T., Preparata F.P. Location of a point in a planar subdivision and its applications // SIAM Journal on Computing, 1977, Vol. 6, No. 3, pp. 594-606.

50. Christos Levcopoulos and Drago Krznaric. Quasi-greedy triangulations approximating the minimum weight triangulation. In Proc. 7th ACM-SIAM Sympos. Discrete Algorithms, pages 392-401, 1996.

51. Lloyd E. On triangulation of a set of points in the plain. MIT La. Сотр. Sc. Tech. Memo., N285o. 88, 1977. 56 p.

52. E. L. Lloyd. On triangulations of a set of points in the plane. In Proc. 18th Annu. IEEE Sympos. Found. Comput. Sci., pages 228-240, 1977.

53. N. Megiddo. Linear programming in linear time when the dimension is .xed. J. ACM, 31:114-127, 1984.

54. M. S. Paterson and F. F. Yao. E±cient binary space partitions for hidden-surface removal and solid modeling. Discrete Comput. Geom., 5:485-503, 1990.

55. O'Rourke J., Chien C.-B., Olson Т., Naddor D. A new linear algorithm for intersecting convex polygons // Computer Graphics and Image Processing, 1982, Vol. 19, pp. 384-391.

56. O'Rourke, E. Demaine, J. Mitchell "The Open Problems Project 2003"

57. J. O'Rourke and I. Streinu. Vertex-edge pseudo-visibility graphs: Characterization and recognition. In Proc. 13th Annu. ACM Sympos. Comput. Geom., pages 119-128, 1997.

58. Seth Pettie and Vijaya Ramachandran. An optimal minimum spanning tree algorithm. J. ACM, 49(l):16-34, January 2002.

59. D. Randall, G. Rote, F. Santos, and J. Snoeyink. Counting triangulations and pseudotriangulations of wheels. In Proc. 13th Canad. Conf. Comput. Geom., pages 149-152, 2001.

60. A. Saalfeld. Joint triangulations and triangulation maps. In Proc. 3rd Annu. ACM Sympos. Comput. Geom., pages 195-204, 1987.

61. Jonathan Richard Shewchuk. Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates. Discrete & Computational Geometry 18.1. C. 305-363,1997.

62. Jonathan Richard Shewchuk. Robust Adaptive Floating-Point Geometric Predicates, Proceedings of the Twelfth Annual Symposium on Computational Geometry, ACM, May 1996.

63. Jonathan Richard Shewchuk. Routines for Arbitrary Precision Floating-point Arithmetic. Last revised May 18, 1996.

64. R. Seidel. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Comput. Geom. Theory Appl., l(l):51-64, 1991.

65. Skiena, S. S. "Triangulation." §8.6.3 in The Algorithm Design Manual. New York: Springer-Verlag, pp. 355-357, 1997.

66. J. Snoeyink. Point location. In Jacob E. Goodman and Joseph O'Rourke, editors, Handbook of Discrete and Computational Geometry, chapter 30, pages 559-574. CRC Press LLC, Boca Raton, FL, 1997.

67. R. E. Tarjan and C. J. van Wyk, An 0(n log log n)-time algorithm for triangulating a simple polygon, SIAM Journal of Computing, 17(1), 143-178 (1988).