Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
2.2. Задачи локализации точки
67
ций. Поэтому сразу же возникают два вопроса: (1) Какова стоимость процедуры дискриминации точки относительно произвольной цепи и существуют ли такие цепи, дискриминация относительно которых проста? (2) Какова трудоемкость поиска подходящей разделяющей цепи?
Рассматривая первый вопрос, легко убедиться, что дискриминация относительно произвольной цепи есть, по существу, та же
Рис. 2.11. Примеры цепей: (а) — общего вида; (Ь) — монотонная по отношению к прямой /.
самая задача, что и проверка принадлежности обыкновенному многоугольнику. Поэтому необходимо поискать более ограниченный класс цепей. Один из таких классов задается следующим определением.
Определение 2.2. Цепь С = (щ, ..., ир) называется монотонной по отношению к прямой /, если любая прямая, ортогональная к /, пересекает С ровно в одной точке.
Другими словами, любая монотонная цепь С принадлежит к определенному выше типу (2), а ортогональные проекции 1(ир)} вершин С на I упорядочены вдоль / следующим образом: l(ui), ..., 1(ир).
Одна из подобных цепей показана на рис. 2.11 (Ь). Очевидно, что проекцию l(z) заданной пробной точки z на / можно локализовать методом двоичного поиска в единственном из интервалов (l(iii), l(ui+i)). Затем единственная линейная проверка покажет, по какую сторону от прямой, несущей ребро лежит пробная точка z. Поэтому дискриминация произвольной точки относительно р-вершинной цепи реализуется за время 0(log р)1).
') Заметим, что монотонную цепь можно считать предельным случаем звездного многоугольника.
68
Гл. 2. Геометрический поиск
Такая эффективность побуждает использовать монотонные цепи при локализации точек. Предположим, что существует некое множество "g7 = {Си . . . , Сг) цепей, монотонных относительно одной и той же прямой / и обладающих следующими дополнительными свойствами:
Свойство 1. Объединение всех элементов содержит заданный ППЛГ G
Свойство 2. Для любой пары цепей С, и С,- из ^ те узлы С,, которые не являются узлами С,-, лежат по одну сторону от С/.
Такое множество W называется полным множеством монотонных цепей графа G. Заметим, что, согласно свойству 2, "цепи из полного множества упорядочены. Следовательно, можно применить к W метод дихотомии (т. е. двоичный поиск), в котором элементарной операцией вместо простого сравнения чисел теперь будет дискриминация точки относительно цепи. Итак, если у нас г цепей в Ч? и в самой длинной цепи р вершин, то поиск займет в наихудшем случае О (log г- log р) времени.
Но остается самый важный вопрос: можно ли построить полное множество монотонных цепей для произвольного ППЛГ G? Ответ на этот вопрос отрицательный. Однако мы покажем, что ППЛГ допускает построение полного множества монотонных цепей, если удовлетворяет довольно слабому ограничению. Кроме того, мы покажем, что произвольный ППЛГ можно легко преобразовать в такой граф, к которому применима процедура построения цепей. Эта процедура создает несколько новых «искусственных» областей, которые не мешают, однако, эффективному решению задачи локализации точки.
Следующее определение выражает упомянутое выше слабое ограничение:
Определение 2.3. Пусть G — ППЛГ с множеством вершин {и\, vN), где вершины индексированы так, что i <. j тогда и только тогда, когда г/(и,)< y(v,), или y(vi) = y(v,) и x(vt)> >x(vj). Вершина Vj называется регулярной, если существуют такие целые i < / < k, что (vi, Vj) и (v,-, Vk) — ребра G. Говорят, что ППЛГ G регулярен, если каждая его вершина v,- регулярна при 1 < / < N (т. е. за исключением двух крайних вершин Vi и vN).
На рис. 2.12 приведен пример регулярного графа. Сейчас мы покажем, что регулярный граф распадается на полное множество цепей, монотонных относительно оси у. (Далее прямая / будет считаться осью у на плоскости.)
') Заметим, что конкретное ребро G может принадлежать более чем одной цепи из
2.2. Задачи локализации точки
69
Чтобы подтолкнуть интуицию, представим, что ребро (и,-, v,-) ориентировано от и,- к v,, если i < /. Поэтому можно говорить о множествах IN(w/) и OUT (и,) соответственно входящих и исходящих ребер для вершины v,-. Предположим, что ребра в jN(t),-) упорядочены по углу против часовой стрелки, а ребра в ~ОиТ(г>/) упорядочены по часовой стрелке, llo предположению о регулярности оба эти множе-ства не пусты для каждой из некрайних вершин. Отсюда видно, что для ЛЮбоЙ vj (j ф 1) можно построить «/-монотонную цепь от v\ до vj. Это тривиально для / = 2. Допустим, что данное утверждение верно для всех k < /. Поскольку vj регулярна, то по определению 2.3 существует такое *'</, что (у,-, и,) —ребро G. Но по предположению индукции существует цепь С от v\ до vi, монотонная относительно оси у; ясно, что сцепление С с (vi,vj) — тоже монотонная цепь. Для завершения доказательства необходимо показать, что вы- Рис- 2-12- Пример регулярного полнены свойства 1 и 2, упомяну- ППЛГ. тые выше. Пусть вес W(e) ребра е — это число цепей, которым принадлежит е. Кроме того, введем следующие обозначения:
