Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Предыдущее обсуждение намечает все существенные черты метода плоского заметания. Есть вертикаль, которая заметает плоскость слева направо, останавливаясь в особых точках, именуемых «точками событий». Пересечение заметающей прямой с входными данными задачи содержит всю полезную для продолжения поиска информацию. Итак, мы имеем две основные структуры:
1. Список точек событий — последовательность абсцисс, упорядоченных слева направо и определяемых позициями остановок заметающей прямой. Отметим, что список точек событий не требуется обязательно извлекать полностью из исходных данных, вместо этого его можно динамически обновлять при работе алгоритма плоского заметания. В разных приложениях для этого могут понадобиться различные структуры данных.
2. Статус заметающей прямой — адекватное описание пересечения этой заметающей прямой с заметаемой геометрической
22
Гл. 1. Введение
структурой. «Адекватное» означает, что это пересечение содержит информацию, полезную для данного приложения. Статус заметающей прямой обновляется в каждой точке событий, а подходящая для него структура данных должна выбираться применительно к каждому случаю.
Примеры алгоритмов плоского заметания можно найти в разд. 2.2.2.
1.2.3. Структуры данных
Геометрические алгоритмы включают в себя манипулирование с объектами, которые не обрабатываются на уровне машинного языка. Поэтому пользователь должен описать эти сложные объекты посредством более простых типов данных, непосредственно представимых в машине. Такие описания принято называть структурами данных.
Самые распространенные сложные объекты, встречающиеся при построении геометрических алгоритмов, — это множества и последовательности (упорядоченные множества). Структуры данных, особенно удобные для этих сложных комбинаторных объектов, хорошо описаны в стандартной литературе по алгоритмам, к которой и отсылается читатель [Aho, Hopcroft, Ullman (1974); Reingold, Nievergelt, Deo (1977)]. Приведем их здесь только затем, чтобы бегло очертить классификацию этих структур данных наряду с функциональными возможностями и вычислительной эффективностью.
Пусть 5 — некоторое множество, представленное структурой данных, и пусть и — произвольный элемент некоторого универсального множества, подмножеством которого является S. Приведем основные операции, встречающиеся при работе со множествами:
1. ПРИНАДЛЕЖНОСТЬ (и, S).Верно, что «eS? (Ответ типа ДА/НЕТ.)
2. ВСТАВИТЬ (и, S). Включить и в S.
3. УДАЛИТЬ (и, S). Исключить и из 5.
Предположим теперь, что {5Ь S2, ..., S*}— набор множеств (попарно непересекающихся). На этом наборе полезны следующие операции:
4. НАЙТИ {и). Найти такое /, что и е 5/.
5. ОБЪЕДИНИТЬ (S/, S;; Sk). Сформировать объединение St и 5/ и назвать его Sk.
1.2. Алгоритмические основы
Если универсальное множество полностью упорядочено, то очень важны следующие операции:
6. MIN (S). Найти наименьший элемент 5.
7. РАСЦЕПИТЬ (и, 5). Разделить 5 на {Sh S2} такие, что Si = {v. v <= 5 и v «}, а S2 = 5 — Sb
8. СЦЕПИТЬ (Si, S2). Предположим, что для любых u'eS| и и" е Sj имеем и'^.и"\ следует сформировать множество
S = S, и s2.
Структуры данных можно классифицировать на базе операций, которые на них допустимы (без учета их эффективности). Так, для упорядоченных множеств имеется следующая таблица:
Таблица I
Структура данных
Допустимые операции
Словарь
ПРИНАДЛЕЖНОСТЬ, ВСТАВИТЬ, УДАЛИТЬ
Приоритетная очередь
MIN, ВСТАВИТЬ, УДАЛИТЬ
Сцепляемая очередь
ВСТАВИТЬ, УДАЛИТЬ, РАСЦЕПИТЬ, СЦЕПИТЬ
Для лучшей эффективности каждая из этих структур данных обычно реализуется как дерево двоичного поиска, сбалансированное по высоте (часто как АВЛ- или 2-3-дерево) [Aho, Но-pcroft, Ullman (1974)]. При такой реализации каждая из вышеописанных операций осуществляется за время, пропорциональное логарифму числа элементов, хранимых в структуре данных; требуемая память пропорциональна мощности исходного множества.
Описанные выше структуры данных можно мысленно представить себе в виде линейного массива из элементов (списка) так, что вставки и удаления можно осуществить в любой позиции этого массива. Иногда для каких-то приложений вполне приемлемы некоторые более ограниченные режимы доступа, допускающие упрощение. Приведем эти структуры: очереди — вставки происходят с одного конца, а удаления — с другого; стеки — и вставки, и удаления происходят с одного конца (вершины стека). Очевидно, что все, что необходимо для управления соответственно стеком или очередью, — это один или два указателя. Для краткости мы будем пользоваться обозначениями «=>U» и «?/=*-» для указания соответственно добавления или удаления из U, где U — это очередь или стек.
24
Г л. 1. Введение
Неупорядоченные множества всегда могут обрабатываться, как упорядоченные: путем искусственного введения порядка над их элементами (например, присвоением «имен» элементам и использованием алфавитного порядка). Типовая структура данных в этой ситуации такова:
Таблица II
