Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
2.2. Задачи локализации точки
ментов. Поскольку обе задачи (поиска медиан и балансировки) требуют в сумме О (N log N) времени, то все построение структуры данных поиска завершается за время О (Л/ log Л/). Второе утверждение таково: поскольку структура данных поиска имеет О-узел для каждого фрагмента ребра и V-узел для каждой вершины, то используемая память также оценивается через О(NlogN) '). Подводя итог, имеем:
Теорема 2.8. Точку можно локализовать в N-вершинном планарном подразбиении менее чем за 4 log2 N проверок, с использованием О (N log N) памяти и такого же времени предобработки.
Примечание 1. Ранее мы отложили обсуждение вопроса о построении упорядочения множества ребер Е, согласованного с отношением частичного порядка «<», задаваемого определением 2.6. Для достижения этой цели можно употребить метод,
Рис. 2.25. Пример вычисления отношения «¦«» как результата обработки вершины v. В случае (а) порождается пара (е\, е2); в случае (Ь) порождаются пары (еье2), (е2, е3) и (е3,е4).
являющийся простой модификацией плокого заметания, описанного в разд. 2.2.2.2 для «регуляризации» плоского графа.
В процессе заметания сверху вниз вершины графа G просматриваются, а статус заметающей прямой корректируется так, как описано выше. Побочным результатом этого заметания является регистрация смежности всех ребер, получаемая при их вставлении или удалении. Отношение смежности, выражаемое в виде упорядоченной пары ребер (левое, правое) (рис. 2.25), является транзитивным сведением ««» искомого частичного упорядочения. Очевидно, что если граф G имеет N вершин, то отношение ««» можно вычислить за время 0(N\ogN). Если известно отношение ««», то искомое упорядочение можно
') В худшем случае затраты памяти действительно составляют O(NlogN). Однако для ППЛГ специального вида [Bilardi, Preparata (1981)] требуется памяти в среднем O(N), что заставляет предполагать аналогичное поведение в среднем и для ППЛГ общего вида.
Гл. 2. Геометрический поиск
получить за время 0(Л7) стандартным методом топологической сортировки [Knuth (1973) >)]•
Примечание 2. Описанный метод не ограничивается лишь ППЛГ. В самом деле, прямолинейные отрезки можно заменить другими кривыми, если будут выполнены следующие два условия: (1) эти кривые — однозначные функции от одной избранной координаты (скажем, от у); (2) дискриминацию точки относительно любой из таких кривых можно проделать за константное время. Например, эти условия, очевидно, выполняются для дуг окружностей и других коник, которые не имеют горизонтальных касательных к неконцевым точкам. Применение метода Киркпатрика (разд. 2.2.2.3) в подобной ситуации представляет очевидные трудности, поскольку требуется перетриангулировать многоугольник с криволинейными ребрами.
2.3. Задачи регионального поиска
2.3.1. Общие замечания
Как было показано в разд. 2.1, задачи регионального поиска можно рассматривать как двойственные, в определенном смысле, к задачам локализации точки, которые уже были рассмотрены.
Здесь файлом будет считаться набор записей, каждая из которых идентифицирована упорядоченным d-плексом «ключей» (Х\, х2, Xd). Естественно считать rf-плекс ключей точкой в rf-мерном декартовом пространстве. На таком файле можно допустить некоторые действия пользователя, или запросы. Однако в данном контексте мы будем иметь дело исключительно с региональными запросами. Запрос определяет область (регион) в d-мерном пространстве, а результатом поиска является отчет о подмножестве точек файла, содержащихся в этой запрашиваемой области. Другой, более ограниченной целью поиска является простой подсчет числа точек в запрашиваемой области. (Единый подход к этим двум типам задач получится, если каждую запись сопоставить с одним из элементов коммутативной полугруппы с операцией «*» и считать, что запрос реализует операцию «*» над всеми записями в своем интервале. Тогда в режиме отчета каждой записи сопоставлено ее имя, а «*» есть операция объединения подмножеств; в режиме подсчета каждой записи сопоставлено целое число 1, а «*» есть обычное сложение [Fredman (1981)].)
Представление в декартовом пространстве является абстракцией для множества очень важных приложений, часто пмеиуе-
>) См. русское издание: Кнут, т. 1, с. 323. — Прим. персе.
2.3. Задачи регионального поиска
мых «поиском по многим ключам» (Knuth (1973), v. 3J. Например, отдел кадров компании может пожелать узнать число работников в возрасте от 30 до 40 лет, зарабатывающих от 27 000 до 34 500 долларов в год. Помимо данного выдуманного примера приложения подобного рода возникают в географии, статистике [Loftsgaarden, Queensberry (1965)] и автоматизации проектирования [Lauther (1978)].
Возвращаясь к нашей абстрактной задаче, заметим, что запросы уникального типа не представляют интереса, ибо их обработка непременно сведется к какому-нибудь виду исчерпывающего перебора в пространстве. Поэтому сосредоточимся на массовых запросах, и тогда потребуются изначальные затраты на предобработку и запоминание, чтобы в долгосрочном плане получать выигрыш во времени поиска. В этом смысле нашей конечной целью является решение данной задачи в ее самом широком обобщении, т. е. умение работать в пространстве произвольной размерности и на множестве произвольных областей запроса как по форме, так и по размеру. В то время как вопрос о размерности пространства можно адекватно разрешить (за определенную вычислительную плату, разумеется), к сожалению, большая часть того, что известно сегодня относительно природы запроса, связано с гиперпрямоугольными областями. (Гиперпрямоугольная область — это декартово произведение интервалов на различных координатных осях1). Хотя случай гиперпрямоугольной области и очень важен, он, несомненно, не охватывает всех желамых форм. Например, поиск всех точек на ограниченном расстоянии d от пробной точки г, называемый поиском на ограниченном расстоянии, порождает сферическую область поиска (т.е. гиперсферу радиусом d с центром в г). Как будет показано ниже, методы, успешно применяемые в ги-перпрямоугольном случае, неприменимы в случае сферы. Если для сферы когда-нибудь и удастся достичь сравнимой эффективности, то получена она будет, вероятно, на основе совершенно иных принципов. На самом деле, имеются кое-какие недавние продвижения [Chazelle, Cole, Preparata, Yap (1984)] в задаче поиска на ограниченном расстоянии при d = 2 (задача кругового регионального поиска), основанные на понятии «близости»;
