Ближайшая пара точек плоского случая - PullRequest
Новая
       27

Ближайшая пара точек плоского случая

0 голосов
/ 25 апреля 2011

Я смотрю на запись в Википедии, чтобы решить эту проблему.В нем перечислены пять шагов

1.Сортировка точек по координате x

2.Разрезать набор точек на два подмножества одинакового размера вертикальной линией x = xmid

3. Решите проблему рекурсивно в левом и правом подмножествах.Это даст минимальные расстояния для левой и правой сторон dLmin и dRmin соответственно.

4. Определите минимальное расстояние dLRmin среди пары точек, в которой одна точка лежит слева от делительной вертикали ивторая точка находится справа.

5. Окончательный ответ - минимум среди dLmin, dRmin и dLRmin.

Четвертый шаг: у меня проблемы с пониманием.Как выбрать точку слева от линии для сравнения с точкой справа от линии.Я знаю, что не должен сравнивать все точки, но мне неясно, как выбирать точки для сравнения.Пожалуйста, не присылайте мне ссылку, я искал, перешел на многочисленные ссылки и не нашел объяснения, которое помогает мне понять шаг 4.

Спасибо

Аарон

1 Ответ

2 голосов
/ 25 апреля 2011

Ответ на ваш вопрос был в следующем абзаце статьи в Википедии:

Оказывается, что шаг 4 может быть выполняется за линейное время. Опять наивный подход потребует расчет расстояний для всех лево-правые пары, т.е. в квадратичной время. Ключевое наблюдение основано на следующее свойство разреженности точка установлена. Мы уже знаем, что ближайшая пара точек не дальше кроме dist = min (dLmin, dRmin). Поэтому для каждой точки р слева от разделительной линии мы должны сравнить расстояния до точек которые лежат в прямоугольнике размеры (dist, 2 * dist) до справа от разделительной линии, как показано на рисунке. И более того, это прямоугольник может содержать не более 6 точек с попарными расстояниями не менее dRmin. Поэтому достаточно вычислить не более 6n влево-вправо расстояния в шаге 4. Повторение отношение к числу шагов может записывается как T (n) = 2T (n / 2) + O (n), который мы можем решить с помощью мастера теорема для получения O (n log n).

Не думаю, что могу выразиться намного яснее, чем они уже есть, но есть ли у вас какие-либо конкретные вопросы об этом шаге алгоритма?

...