Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Теорема 5.4 [Bentley, Shamos (1976)]. Пусть в Ed задано множество S, содержащее N точек. Существует гиперплоскость I, перпендикулярная одной из координатных осей и обладающая следующими свойствами:
(1) каждое из подмножеств S; и S2 множества S, расположенных по обе стороны от I, содержит не менее N/ (Ad) точек;
(2) 8-слой пространства Ed, расположенный около гиперплоскости I, содержит не более dbNl~l/d точек, где б = min (бь б2), б,- — минимальное расстояние между точками множества Si (i = 1, 2), а Ь — верхняя граница числа точек, содержащихся в гиперкубе со стороной 26 и удаленных друг от друга на расстояние не менее б.
Доказательство. Проведем доказательство для d = 2, так как в этом случае можно непосредственно опереться на интуи-
246
Гл. 5. Близость: основные алгоритмы
цию. Доказательство для d-мерного случая проводится аналогичным образом. С несущественной потерей общности можно считать, что N кратно 8. Определим по оси х интервал [лт.хг] таким образом, чтобы слева от хх и справа от х2 находилось по А78 точек множества S. Обозначим через Cj?S множество точек с абсциссами между х\ и х2. Заметим, что | С* | = ЗЛ//4. Аналогичным образом определим интервал [г/ь г/2] по оси у. Обозначим через R декартово произведение [хи х2]Х[уи Уг\ (рис. 5.14).
Определим на оси х наибольший интервал, целиком попадающий в [яь-Кг] и содержащий проекции 2bNl/2 точек. Аналогичный интервал определим на оси у. Обозначим через у длину наибольшего из этих двух интервалов. Не теряя общности, будем считать, что таким интервалом является \х[, х2] X Х( [х[, х'2~\ cz [jcp х2~\). Утверждается, что прямая /, задаваемая
Рис. 5.15. Взаимосвязь между [хи х2] и [xj, дг2].
уравнением х = {х\-{- x'2)j2 (прямая, перпендикулярная оси х и делящая отрезок х\х'2 пополам), удовлетворяет условиям (1) и (2) теоремы (рис. 5.15).
Для доказательства этого утверждения покажем сначала, что неравенство у < 26 не может иметь места. А затем пока-
5.4. Решение задачи о ближайшей паре
247
жем, что условие у ^ 26 обеспечивает необходимый результат.
Условие у < 26 означает, что любая горизонтальная или вертикальная полоса шириной 26, проекция которой попадает внутрь [yi,y2] или [xi,x2] соответственно, содержит больше чем 2bN1/2 точек.
Разделим интервал [хх, х2) на подынтервалы длиной 26. Каждая вертикальная полоса, проецируемая на такой подынтервал, содержит более 2bN1/2 точек. Так как имеется Цх2—
— xi)/26J таких интервалов,то получаем L(х2-x,)/26J • 2bN"2 <\СХ\ = ЗЛ//4,
или
L(je2-x,)/2A]<3tf«78&.
Аналогичные рассуждения для интервала [г/ьг/г] приводят к неравенству
1(у2-Ух)/2ь\<змч2/8ь.
Рассмотрим теперь прямоугольник R = [хх, х2] X [уи У2] • Этот прямоугольник содержит не более \ (х2— х\) /261 ¦ f (у2 —
— у\) /261 квадратов со стороной 26. Так как сторона каждого такого квадрата равна 26, то по условию теоремы каждый квадрат содержит не более Ъ точек. Отсюда следует, что число точек множества 5, содержащихся в R, не превосходит
<№+•?•»•
Так как Ь — это небольшая по величине константа, большая или равная 1, то правая часть этого неравенства принимает максимальное значение при 6 = 1. Таким образом, R содержит не более 2(3/8)2Л^~0,28Я точек при условии, что N^8.
С другой стороны, вертикальные полосы, находящиеся вне интервала [хь^г], содержат 2-N/8 точек, и то же самое справедливо для горизонтальных полос, находящихся вне интервала [ух,у2] (см. рис. 5.15). В соответствии с принципом включения-исключения, число точек вне R не превышает 4N/8 = = N/2, и, следовательно, R содержит не менее N/2 точек. Полученное противоречие указывает на то, что неравенство у < < 26 не выполняется.
Так как у ^ 26, то сразу же получаем требуемый результат: выполнение свойства (1) обеспечивается способом построения интервала [х1,лг2], а свойство (2) выполняется в силу
248
Гл. 5. Близость: основные алгоритмы
того, что б-слой около прямой / содержит не более 2bNl/2 точек. Таким образом, прямая / удовлетворяет условиям теоремы.
Мы используем эту теорему для того, чтобы показать прежде всего, что на шаге 1 алгоритма БПАРАс?(5) можно так выбрать разделяющую гиперплоскость /, что будет иметь место неравенство l/4d < а ^ 1 — \/4d, а 5)2 — множество точек в б-слое около /—будет иметь мощность не более cdNl~1/d, где с = 4-За~1. Действительно, если б — min(6b б2), то гиперкуб со стороной 26, находящийся в б-слое, содержит не более с = = 4-3d_I точек, в чем можно легко, убедиться с помощью индукции по d. Индукция начинается со значения d = 2, для которого, как уже было показано, гиперкуб со стороной 26 содержит не более 12 точек. Тем самым доказывается, что разделяющая гиперплоскость I существует. Для ее определения выполним предварительно сортировку множества S по всем координатам, затратив на это время О (dN log N). Путем простого просмотра за время O(dN) получившихся в результате сортировки упорядоченных последовательностей определяем интервалы такие, что по обе стороны от них содержится по N/4d точек. В каждом из этих интервалов, опять-таки используя простой просмотр, можно за время O(N) определить максимальные длины окон (подынтервалов), содержащих в точности \cdNx-'[/d\ точек. Наибольший из этих подынтервалов определяет единственную координатную ось и разделяющую гиперплоскость, которая делит его пополам. Заметим, что исключительно благодаря предварительной сортировке разделяющую гиперплоскость можно найти за линейное по размеру множества S время.
