Cтраница 2
Обычно эти исследования демонстрируют общее правило, известное из практики построения алгоритмов, а именно взаимозависимость между различными мерами эффективности. Задача регионального поиска не составляет исключения; в таблице I показаны затраты при комбинировании ресурсов. [16]
Однако в некоторых случаях отдельные виды этих методов неприменимы. Например, при региональных поисках неприменимы мелкомасштабные съемки из-за недостаточной обнаженности площади, характера и мощности наносного покрова. [17]
Применение диаграммы Вороного дает изящный метод получения довольно эффективного решения задачи кругового регионального поиска. Задача заключается в следующем: на плоскости заданы множество 5, содержащее N точек, и окружность С с центром в точке q ( запрос); требуется перечислить точки множества 5, попавшие внутрь С. Как обычно для задач регионального поиска, цель заключается в достижении оценки 0 ( f ( N) k), где k - размер множества точек, соответствующих запросу. Если эта цель достижима, то алгоритм характеризуется парой ( M ( N) f ( N)), где M ( N) - требуемый объем памяти. [18]
Следуя подходу, введенному в разд. S из N точек на плоскости, и проведем горизонтальную и вертикальную прямые через каждую из этих точек. Разумеется, эти прямые разобьют плоскость на ( N I) 2 прямоугольных ячеек. Другими словами, пары ячеек формируют классы эквивалентности относительно результатов регионального поиска. [19]
После такого напоминания не составит труда воспользоваться деревом отрезков при региональном поиске. Начнем, как обычно, с двумерного случая. Дерево отрезков 7 ( 1, N) используется при поиске по х - координате. Каждый такой узел v соответствует множеству из ( E [ v ] - B [ v ]) абсцисс ( определения даны в разд. Ординаты этих точек образуют обычное прошитое двоичное дерево для регионального поиска в ( / - направлении. [20]
Что касается регионального поиска, то в разд. & - /) - дерева), обладает большим временем поиска. Поэтому кажется, что избыток памяти является ключевым условием быстрого поиска. Как метод прямого доступа, так и метод дерева регионов служат примерами этой идеи. В действительности это примеры приложений, названных Бентли и Сэйксом задачами поиска, допускающими декомпозицию [ Saxe, Bentley ( 1979) ], в которых ответ на запрос относительно всего пространства получается как комбинация ( в данном случае как сумма) ответов на запросы относительно подходящего набора частей этого пространства. Остается открытым важный вопрос о существовании ( N, log N) - алгоритма для 2-мерного регионального поиска. Недавно Чазелле [ Chazelle ( 1983с) ], используя метод фильтрующего поиска, смог понизить потребность в памяти с N log N ло N log N / og log N, показав тем самым, что N log N не является нижней оценкой. [21]