Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Задача П.1 (РЕГИОНАЛЬНЫЙ ПОИСК — ПОДСЧЕТ). Даны N точек на плоскости. Сколько из них лежит внутри заданного прямоугольника, стороны которого параллельны координатным осям? То есть сколько точек (х, у) удовлетворяют неравенствам а^х^Ь, с ^ у ^ d для заданных а, Ь, с и d (рис. 2.1)?
Очевидно, что уникальный региональный запрос может быть обработан (оптимально) за линейное время, так как надо только проверить каждую из N точек, чтобы увидеть, удовлетворяет ли она неравенствам, задающим прямоугольник. Аналогично необходима линейная затрата памяти, так как следует запомнить только 2N координат. Нет никаких затрат на предобработку, а
') Эта задача будет рассмотрена в полном объеме в разд. 2.3.
54
/л. 2. Геометрический псиск
время корректировки для новой точки равно константе. Какую структуру данных можно использовать для ускорения обработки массовых запросов? Кажется, что слишком трудно найти такое упорядочение точек, чтобы любой новый прямоугольник мог быть легко с ним согласован. Мы не можем также решить эту задачу наперед для всех возможных прямоугольников, так как их число бесконечно. Следующее решение является примером использования метода локусов в геометрических задачах: запросу ставится в соответствие точка в удобном для поиска
Рис. 2.1. Региональный запрос. Сколько точек внутри прямоугольника?.
пространстве, а это пространство разбивается на области (локу-сы) '), в пределах которых ответ не изменяется. Другими словами, если считать эквивалентными два запроса, на которые поступают одинаковые ответы, то каждая область разбиения пространства поиска соответствует одному классу эквивалентности запросов.
Прямоугольник сам по себе — неудобный объект; мы предпочитаем работать с точками. Это означает, например, что можно заменить запрос с прямоугольником четырьмя подзадачами, по одной на каждую из его вершин, и совместить их решения для получения окончательного ответа. В этом случае подзадача, связанная с вершиной р, состоит в определении числа точек Q(p) исходного множества, которые удовлетворяют неравенствам х ^ х(р) и у^у(р), т.е. числа точек в левом нижнем квадранте, определяемом вершиной р (рис. 2.2).
Понятие, с которым мы встретились здесь, — это векторное доминирование (см. также разд. 4.1.3). Говорят, что точка (вектор) v доминирует над w, тогда и только тогда, когда для всех индексов i верно условие у,- ^ wi. На плоскости точка v доминирует над w тогда и только тогда, когда w лежит в левом
') Понятию «локус» соответствует устаревший термин «геометрическое место точек», употребляющийся сейчас лишь в учебной литературе. — Прим.
2.1. Введение в геометрический поиск
55
нижнем квадранте, определяемом v. Итак, Q(p) — число точек, над которыми доминирует р. Связь между доминированием и региональным поиском видна на рис. 2.3. Число точек
U i У(Р)
х(р) , х
Рис. 2.2. Сколько точек «юго-западнее» р?
N(pip2pzPi) в прямоугольнике р\р2ръР\ определяется следующим
образом: ^___»
}~N (Plp2p3p4) = Q (Pl) -?> (p2) - Q Ы + Q (Рз)- J , (2-1)
o I--n.b-l - i:\U) - , --- u" - vl
Это следует из комбинаторного правила включения — исключения [Liu (1968)]: над всеми точками прямоугольника, несомненно, доминирует вершина рь Нужно исключить такие точки, над которыми доминируют р2 и Р4, но это приведет к тому, что часть точек будет исключена дважды, а именно те, над которыми доминируют и р2, и р4, но как раз эти точки лежат в левом нижнем квадранте вершины р3.
Итак, задача регионального поиска сведена к задаче обработки запросов о доминировании для четырех точек. Свойство, облегчаю- Рис 23 регио„аль„ый поиск в форме щее эти запросы, заклю- четырех запросов о доминировании, чается в том, что на плоскости существуют области удобной формы, внутри которых число доминирования Q является константой.
Предположим, что из наших точек на оси х и у опущены перпендикуляры, а полученные линии продолжены в бесконечность. Они создают решетку из (N + I)2 прямоугольников, как показано на рис.2.4.
Для всех точек р в любом из таких прямоугольников (ячеек) Я(р) — константа. Это означает, что доминантный поиск есть
* рг *
Pi
•
•
•
•
•
56
Гл. 2. Геометрический поиск
просто ответ на вопрос: в какой ячейке прямоугольной решетки лежит заданная точка? На этот вопрос особенно легко ответить. После упорядочения исходных точек по обеим координатам останется только выполнить два двоичных поиска (по одному для каждой оси), чтобы найти ячейку, содержащую нашу точку. Значит, время запроса будет равным только O(logiV). К сожалению, имеется 0(N2) ячеек, поэтому будет нужна квадратичная память. Нужно, конечно, вычислить число доминирования
V
O11J2J3J4J5J6J7
-----4„„4._.4„4„_+_„^----+ —
0|1|1|2|3}4}5 {6
О j 1 [ 1 { 2 J 3 J 3 } 4 ! 5
-----4-__+_„ + __>._. + _„1----4----
О ! 1 | 1 j 2 ! 2 ! 2 ! 3 | 4
o|o|o!i!i!ij 1 ! 2
о j о ! о | о ! о | о ! о 1 о
Рис. 2.4. Прямоугольная решетка для доминантного поиска.
