Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
2(ЛЛ + ЛГ2+ ... +Л/Мло)<2Л'1(1+а + а2+ ...
(заметим, что Ni = N по определению). Что касается памяти, используемой под указатели, то по свойству 2 каждый узел имеет не более Н указателей; поэтому не более 2NH/(\—а) указателей появится в Т. Это доказывает последнее утверждение.
Теперь надо показать, что существует такой критерий выбора множества удаляемых вершин, при котором выполняются свойства 1 и 2. Вот этот критерий: «Удалить несмежные вершины со степенью меньше К» (здесь /С —целое число, которое оудет тщательно подобрано). Порядок просмотра и, если необходимо, удаления этих вершин произволен: начинаем с любой из" них, помечаем ее соседей (они не могут удаляться) и продолжаем, пока еще остаются непомеченные вершины.
Введение данного критерия — это удачный прием. Выполнение свойства 2 обеспечивается тривиально. Поскольку удаление вершины со степенью меньше К приводит к образованию многоугольника с числом ребер менее К, то каждый из удаленных тругольников пересекает не более К — 2 А, Н новых треугольников. Для проверки выполнения свойства 1 необходимо воспользоваться некоторыми особенностями плоских графов. Хотя есть возможность провести более детальный анализ, приводящий к лучшим результатам, но следующие соображения достаточны для доказательства необходимого нам утверждения.
2.2. Задачи локализации точки
79
(1) Из формулы Эйлера для плоских графов, в частном случае триангуляции, ограниченной тремя ребрами, следует, что число вершин N и число ребер е связаны соотношением
e = 3N-6.
(2) Пока в триангуляции есть внутренние вершины (в противном случае задача тривиальна), степень каждой из трех граничных вершин не меньше трех. Поскольку существует 3/V — 6 ребер, а каждое ребро инцидентно двум вершинам, то сумма степеней всех вершин меньше 6N. Отсюда сразу следует, что не менее N/2 вершин имеет степень меньше 12. Следовательно, пусть К = 12. Пусть v — это число выбранных вершин: поскольку каждой из них инцидентно не более К— 1 = 11 ребер, а три граничные вершины не выбираются, то мы имеем
Следовательно, а ^ 1 — 1/24 < 0,959 < 1, что доказывает справедливость свойства 1. Безусловно, наш грубый анализ дает оценку а, непрактично близкую к 1, и оценка данного метода, полученная в результате этого анализа, вероятно, хуже, чем оценка, которую покажут численные эксперименты.
Теорема 2.7. Локализацию точки в N-вершинном планарном подразбиении можно осуществить за время О (log Л/) с использованием O(N) памяти, если O(NlogiV) времени ушло на предобработку.
Другое доказательство этой теоремы, основанное на уточнении метода цепей, кратко описано в разд. 2.4.
2.2.2.4. Метод трапеций
Хотя вопрос о существовании оптимального метода локализации точки теоретически уже решен, а в литературе уже представлены и практически оптимальные алгоритмы, описанные в предыдущем разделе, но более привлекательным методом может оказаться такой, асимптотическое поведение которого в худшем случае, возможно, и неоптимально, о чем говорилось в разд. 1.2.1. Другими словами, желаемой целью может оказаться компромиссный подход, основанный на прямой процедуре поиска при, возможно, немного неоптимальной затрате памяти. Сейчас будет описан метод трапеций, который, по-видимому, удовлетворяет этим требованиям [Preparata (1981); Bilardi, Preparata (1981)] »).
Существуют несколько путей неформального изложения идеи
') Экспериментальные наблюдения, опубликованные в [Edahiro et al. (1983)], подтвердили эти ожидания.
Гл. 2. Геометрический поиск
этого метода. Возможно, наиболее естественный путь — считать его развитием метода полос, принадлежащего Добкину и Лип-тону и описанного в разд. 2.2.2.1. Как указано ранее, этот метод имеет чрезвычайно простую процедуру поиска — О (log Л/), но использует досадно много памяти—0(N2) в худшем случае. Последнее обстоятельство имеет место благодаря возможному наличию «длинных» ребер в ППЛГ; длинным считается ребро, пересекающее несколько полос и, следовательно, разбиваемое на такое же число фрагментов. Интересно, что длинные ребра — проклятие метода полос —могут стать преимуществом в методе трапеций. В самом деле, длинное ребро е так удобно разрезает ППЛГ, что горизонтальные полосы по каждую сторону от е образуют полностью независимые структуры (в то время как в методе Добкина — Липтона е находится внутри полосы). В результате плоскость будет разбита на трапеции, как определено ниже.
Определение 2.5. Трапеция имеет две горизонтальные стороны и может иметь две, одну или нуль боковых сторон, причем боковые стороны, если они есть, являются ребрами ППЛГ (или их частями) и никакое другое ребро ППЛГ не пересекает обе ее горизонтальные стороны.
Поиск осуществляется путем локализации пробной точки в последовательности вложенных трапеций, до тех пор пока эта последовательность не закончится такой трапецией, внутри которой нет ребер ППЛГ или их фрагментов. Будет показано, что в этом методе ребро разбивается не более чем на 21og2/V фрагментов в худшем случае, что существенно улучшает оценку памяти, сохраняя О (log N) — оценку времени поиска метода Добкина — Липтона (с незначительным ухудшением константы).
