Научная литература
booksshare.net -> Добавить материал -> Математика -> Препарата Ф. -> "Вычислительная геометрия: Введение" -> 39

Вычислительная геометрия: Введение - Препарата Ф.

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Под редакцией Ю. М. Банковского — М.: Мир, 1989. — 478 c.
ISBN 5-03-001041-6
Скачать (прямая ссылка): vichgeometr.pdf
Предыдущая << 1 .. 33 34 35 36 37 38 < 39 > 40 41 42 43 44 45 .. 180 >> Следующая


Возвращаясь к локализации точки, покажем теперь, как методология фильтрующего поиска и структура указателей Уилларда — Люкера могут быть объединены с методом цепей [Edelsbrunner, Guibas, Stolfi (1985)]. В структуре первичного дерева (где каждый узел v связан с одной из монотонных це-

') Исходные предварительные идеи этого подхода можно проследить в работе [Bentley, Maurer (1979)].

2.4. Замечания и комментарии

пей С) есть указатель от и к вторичной структуре, главной компонентой которой является последовательность T(v), содержащая не только ординаты ребер, отнесенных к цепи С (как в версии Ли — Препараты), но и дополненная, кроме того, каждым вторым членом последовательности, полученной слиянием (дополненных) последовательностей для двух потомков v. Как и в схеме Уилларда — Люкера для дерева регионов, в этой последовательности T(v) поиск выполняется с помощью двоичного дерева только в корне первичной структуры. Для всех остальных узлов доступ к T(v) осуществляется через структуру указателей, что позволяет получить оценку для времени поиска О (log N). За счет распространения «каждого второго члена» с одного уровня на следующий обеспечивается линейных расход памяти, однако при этом, возможно, будет просмотрено вдвое больше областей, чем это необходимо, и их следует профильтровать в духе метода фильтрующего поиска.

Все методы, представленные в этой главе для локализации точки на плоскости, настроены на работу для худшего случая. В классе методов с хорошими оценками в среднем недавно опубликованный метод «черпаков» [Edahiro, Kokubo, Asano (1983)] экспериментально превосходит все ранее изложенные методы, а среди последних лучшую экспериментальную оценку показал метод трапеций.

Что касается регионального поиска, то в разд. 2.3 было показано, что единственный метод, использующий линейную память (метод &-?>-дерева), обладает большим временем поиска. Поэтому кажется, что избыток памяти является ключевым условием быстрого поиска. Как метод прямого доступа, так и метод дерева регионов служат примерами этой идеи. В действительности это примеры приложений, названных Бентли и Сэйксом «задачами поиска, допускающими декомпозицию» [Saxe, Bentley (1979)], в которых ответ на запрос относительно всего пространства получается как комбинация (в данном случае как сумма) ответов на запросы относительно подходящего набора частей этого пространства. Остается открытым важный вопрос о существовании (Л/, log N)-алгоритма для 2-мерного регионального поиска. Недавно Чазелле [Chazelle (1983с)], используя метод фильтрующего поиска, смог понизить потребность в памяти с А/ log N до N log /V/log log Л/, показав тем самым, что N log N не является нижней оценкой.

Другие варианты задачи регионального поиска можно классифицировать по типу области поиска. В одном из таких классов в качестве области поиска выбирают ^-угольник (поиск в многоугольном регионе); предполагая, как обычно, что в файле N точек, Уиллард создал (N, k№-77)-алгоритм [Willard (1982)], который был позже улучшен до (Л/, йЛ/0-695) -алгоритма [Edels-

112

Гл. 2. Геометрический поиск

brunner, Welzl (1983)]. Известен интересный частный случай этой задачи, когда в качестве многоугольного региона берется полуплоскость; для поиска в полуплоскости недавно был предложен оптимальный результат [Chazelle, Guibas, Lee (1983)] (этот метод неприменим, однако, к соответствующей задаче поиска типа подсчета). Очень интересен также случай, когда поисковая область имеет форму круга (круговой региональный поиск, или поиск в диске). Если радиус такого диска фиксирован, то задачу можно решить методом локализации, где плоскость разбита на области так, что все точки в заданной области порождают идентичные ответы. Этот подход можно реализовать, прибегнув, например, к методу трапеций и получив тем самым (Л/3 log Л/, log N)-алгоритм. Однако этот алгоритм намного превзойден (Л/, log N)-методом, предложенным недавно [Chazelle, Edelsbrunner (1984)]. Еще более интересен поиск в переменном диске, где круговая область может обладать произвольным радиусом и центром; лучший из известных методов решения этой задачи имеет сложность (Л/ (log N log log N)2 log N) и будет описан в гл. 6 [Chazelle, Cole, Preparata, Yap (1984)].

Другие задачи поиска работают с различными геометрическими объектами, где пара (запрос, элемент файла) более не соответствует типам: (точка, область) — как при локализации точки или (область, точка) — как при региональном поиске. Например, могут встретиться такие пары, как (многоугольник, многоугольник), (отрезок, отрезок) и т. д.; в подобных случаях искомое отношение скорее является «пересечением», вот почему эти задачи лучше изучить в общем контексте задач о пересечениях (гл. 7). В частности, когда пара (запрос, элемент файла) имеет вид (прямоугольный регион, прямоугольный регион), то получается семейство интересных задач типа пересечения или принадлежности, которые уместнее обсудить в гл. 8.

И наконец, значительный прогресс достигнут при изучении динамических поисковых структур, т. е. таких структур, которые в дополнение к запросам поддерживают операции вставки и удаления. В то время как одномерные динамические структуры (АВЛ-деревья и т. п.) были известны уже более двадцати лет, подступы к решению многомерной задачи начали искать относительно недавно. Следом за пионерской работой Бентли [Bentley (1979)] были разработаны общие методы преобразования статических структур, удовлетворяющих некоторым слабым ограничениям, в динамические.
Предыдущая << 1 .. 33 34 35 36 37 38 < 39 > 40 41 42 43 44 45 .. 180 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed