Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
#(?/*)< d (2d- \)n+h~\ Заметим, что Ue — это проекция U* на ?"; поскольку проецирование является непрерывной функцией, то #(?/е) ^ #(?/*). Вспоминая, что Ф (U) ^ #(^е), мы заключаем:
# (U) < # (Ue) < # (?/') < d • (2d - \)n+h-\ что и является искомым результатом. В самом деле, если (1.13) есть множество ограничений, полученных при прохождении пути в Г от корня к листу, то число неравенств h по величине не превосходит длины этого пути. Отсюда следует, что лист на этом пути связан не более чем с d(2d— 1)«+Л-1 связными компонентами из множества W истинности для данной задачи. Если п* — высота Т (длина наибольшего пути от корня до листа), то Т имеет не более 2''* листов; поскольку каждый лист связан не более чем с d(2d — \)a+h*~l связными компонентами из W, то
#(1Г)<2Н" ¦ d ¦ (2d - l)n+h*~\ или, что то же самое,
.. > logiXlP)___/ilog«(2rf — 1) _ logs - log2 (2rf - 1)
l + log2(2d-l) 1+log, (2d-l) l + log,(2d-l) '
(1.16)
Сформулируем этот важный результат в виде теоремы.
Теорема 1.2'). Пусть W—множество в декартовом пространстве Еп, а Т — алгебраическое дерево решений фиксированного порядка d (d^2), которое решает задачу о принадлежности W. Если h* — высота Т, а Ф(W)— число разделимых связных компонент W, то h* = Я (log #(IP) — л).
Теорема 1.2 включает и случай d = 1, поскольку при любом фиксированном d ^ 2 допустимы и полиномы меньших степеней (простым обнулением коэффициентов при высших степенях). По существу, использование нелинейных полиномов в качестве функций принятия решений не изменяет природу этой задачи радикально; просто наибольшая высота деревьев вычислений уменьшается на мультипликативную константу, зависящую от максимального порядка d. Последняя теорема — краеугольный камень в построениях нижних оценок, которые будут представлены в следующих главах.
') В действительности Бен-Op доказал несколько более сильный результат, независимый от d.
ГЛАВА
Геометрический поиск
Чтобы описать поиск в простейшей абстрактной форме, представим себе, что у нас есть некий набор данных (именуемый файлом) и некоторый новый элемент данных (именуемый образцом). Поиск — это установление связи между образцом и файлом. К вспомогательным, но в принципе не чисто поисковым операциям можно отнести: включение образца в файл, удаление образца из файла, если он был там, и т. п. Как указал Кнут [Knuth (1973)], поиск сводится к определению позиции соответствующей записи (или записей) в данном наборе записей.
Хотя все виды поиска обладают рядом общих базисных черт, его особая геометрическая форма позволяет ставить вопросы со своими неповторимыми нюансами. Во-первых, потому что в геометрических приложениях файлы это не просто «коллекции», как в ряде других областей информатики. Чаще они отображают более сложные структуры, такие как многоугольники, полиэдры и т. п. Хотя случай, скажем, набора отрезков на плоскости выглядит обманчиво бесструктурным, на самом деле каждому отрезку сопоставлены его концы, координаты которых косвенно связаны между собой метрической структурой этой плоскости.
Тот факт, что координаты точек представимы действительными числами, часто ведет к тому, что результатом поиска может оказаться не элемент файла, соответствующий образцу, а скорее положение последнего относительно файла. Это и составляет второе отличие геометрического поиска от обычного.
2.1. Введение в геометрический поиск
В данной главе описываются основные методы геометрического поиска, которые будут использованы в последующих главах для решения более трудных задач. Поисковое сообщение, в соответствии с которым ведется просмотр файла, обыч-
2.1. Введение е геометрический поиск
53
но именуется запросом. От типа файла и от набора допустимых запросов будут сильно зависеть организация первого и алгоритмы обработки последних. Один конкретный пример позволит убедиться, насколько важен этот аспект задачи.
Пусть имеется набор геометрических данных и нужно узнать, обладают ли они определенным свойством (скажем, выпуклостью). В простейшем случае, когда этот вопрос возникает единожды, было расточительством проводить предобработку в надежде ускорить прохождение последующих запросов. Назовем разовый запрос такого типа уникальным. Однако будут и запросы, обработка которых повторяется многократно на том же самом файле. Такие запросы назовем массовыми.
В последнем случае, возможно, стоит расположить информацию в соответствии с некоторой структурой, облегчающей поиск. Однако это можно проделать, только затратив некоторый ресурс, и анализ надо сосредоточить па четырех различных мерах его оценки:
1. Время запроса. Сколько времени необходимо как в среднем, так и в худшем случае для ответа на один запрос?
2. Память. Сколько памяти необходимо для структуры данных?
3. Время предобработки. Сколько времени необходимо для организации данных перед поиском?
4. Время корректировки. Указан элемент данных. Сколько времени потребуется на его включение в структуру данных или удаление из нее?
Различные варианты затрат времени запроса, времени предобработки и памяти хорошо продемонстрированы на следующем примере решения задачи регионального поиска [Knuth (1978), т. З]1), которая часто возникает в географических приложениях и при управлении базами данных:
