Найти наименьшее попарное расстояние между точками в o (n log n)?

11

Следующие упражнения были розданы студентам, которых я курирую:

Учитывая точек на плоскости, разработайте алгоритм, который находит пару точек, расстояние которых минимально среди всех пар точек. Алгоритм должен работать за время o ( n 2 ) .no(n2)

Существует (относительно) простой алгоритм «разделяй и властвуй», который решает задачу за время .Θ(nlogn)

Вопрос 1 : Существует ли алгоритм, который решает данную проблему точно в наихудший момент времени ?o(nlogn)

То, что заставило меня заподозрить, что это может быть возможным, - это результат, который я помню в каком-то разговоре (ссылка приветствуется). В нем говорилось о том, что не более чем постоянное число точек может быть расположено в плоскости вокруг некоторой точки p внутри окружности радиуса r R , где r минимальное расстояние между любыми двумя из участвующих точек , Я думаю, что с = 7 , точки, образующие равносторонний шестиугольник с р в центре (в крайнем случае).cNprRrc=7p

В этом случае следующий алгоритм должен решить их проблему за шагов.n

fun mindist [] | p::[] = INFINITY
|   mindist p1::p1::[] = dist(P[0], P[1])
|   mindist p::r = let m = mindist(r) in
                     min(m, nextNeighbour(p, r, m))
                   end

Обратите внимание, что это (утверждается, что) в линейном времени, потому что только постоянное количество точек rможет быть не дальше, чем mот p(при условии выше утверждение); только эти точки должны быть исследованы для нахождения нового минимума. Конечно, есть подвох; Как вы реализуете nextNeighbour(возможно, с предварительной обработкой в ​​линейное время)?

RpRmR

mmin{dist(p1,p2)p1,p2R}

и

Rp,m:={ppRdist(p,p)m} .

Предположим, что конечно. Можно ли найти с минимальным расстоянием от за (амортизированное) время ? (Вы можете предположить, что строится, добавляя исследуемые точки одну за другой.)Rp,mpRp,mpO(1)Rp

Рафаэль
источник
2
Я бы предложил поиск по "ближайшей паре" в качестве ключевого слова.
Ёсио Окамото
Это все стандартные вещи, смотрите первые две главы здесь: goo.gl/pLiEO
Сариэль Хар-Пелед
Ps. Если вам нужно ожидаемое время, вы можете даже вычислить триангуляцию Делоне, которая содержит минимальное расстояние.
Domotorp
После вопроса 1 вы пишете: «В плоскости вокруг некоторой точки p внутри окружности радиуса r можно расположить не более постоянного числа точек, где r - минимальное расстояние между p и любой другой точкой». Это, конечно, неверно: вы можете взять любое количество точек на окружности радиуса r. Ваше утверждение верно, если r - минимальное расстояние между любыми двумя точками, и в этом случае доказательство довольно простое.
Domotorp
первый вопрос - это учебник, как уже указывалось: безусловно, не исследовательский уровень. я не понимаю второй вопрос: для любого , то вы просите либо не существует , либо является ближайшим соседом в . так как это отличается от вопроса 1? что вы амортизируете (например, если это вопрос структуры данных, какие обновления и запросы)? mppR
Сашо Николов

Ответы:

12

Невозможно решить проблему менее чем за времени в стандартных моделях, например, с использованием алгебраических деревьев решений. Это следует из работ Яо и Бен-Ора, которые показывают, что в этой модели невозможно определить, являются ли все наборы из входных чисел различными или нет (см. Http://people.bath.ac.uk/masnnv /Teaching/AAlg11_8.pdf ). В случае вашей проблемы, представьте, что все они находятся на реальной линии. Если две точки совпадают, то ваши выходные данные будут двумя точками с нулевым расстоянием, а в противном случае - нет, поэтому решение вашей проблемы также решит проблему РАЗЛИЧНЫХ ЧИСЕЛ. Если вы хотите предположить, что все ваши очки разные, то просто добавьте вcnlognniϵxiвходные данные задачи DISTINCT NUMBERS, в этом случае, если ваш вывод не больше , то числа не все различны. (Хотя в этом случае вы должны использовать версию обещания, в которой разница между любыми двумя различными числами составляет не менее , но я думаю, что это же доказательство работает, чтобы показать, что вам также нужен в этом дело.)nϵ2nϵΩ(nlogn)

domotorp
источник
Действительно, спасибо. Это также отвечает на вопрос 2 (отрицательно).
Рафаэль
Проблема, которую вы упоминаете, по-видимому, также известна как проблема разграничения элементов .
Рафаэль
Ссылка @Sariel Har- Peled ( goo.gl/pLiEO ) представляет практический алгоритм линейного времени для поиска ближайшей пары. Этот документ напрямую обращается к этому аргументу и объясняет, что он не применяется, потому что алгоритм использует более мощную модель вычислений.
Кевин Клайн
1
Да, но вопрос специально задан для наихудшего случая времени выполнения. Но я согласен, что все мои наблюдения появляются уже в диссертации Сариэля.
domotorp
0

Насколько я понимаю вопрос 2, алгоритм Рабина также дает своего рода ответ на этот вопрос. На каждом временном шаге структура данных представляет собой сетку с шириной ячейки, меньшей наименьшего расстояния между парами точек, видимых до сих пор, деленного на (так, чтобы ни одна ячейка не содержала более одной точки). Чтобы ответить на вопрос в вопросе 2, вам нужно только сопоставить с ячейкой в ​​сетке и посмотреть на постоянное количество ячеек вокруг нее. Согласно анализу алгоритма, если входной набор точек проверяется в случайном порядке, то амортизированное время обновления для сетки составляет на новую ожидаемую точку. рO(1)2pO(1)

Сашо Николов
источник
Кстати, я имею в виду не ту версию алгоритма, которую описывает Липтон, а то, что она описана в первом комментарии (и в книге Кляйнберга и Тардоса).
Сашо Николов
Только в ожидании, см. Domotorps ответ.
Рафаэль
я не вижу нигде, чтобы вы хотели ограничиться детерминированными алгоритмами. Алгоритм Рабина интересен именно потому, что он обходит нижние границы дерева решений (это похоже на нижние границы для алгоритмов сортировки сравнения и целочисленной сортировки). Кстати, вероятно, есть еще что-то, что использует rabin для обхода нижней границы, а именно трюк хеширования, используемый для доступа к сетке
Сашо Николов
4
«Больше того, что использует Рабин»: также возможность округлять вещественные числа до целых чисел. Нужно быть очень осторожным с этим: если вы настроите модель вычислений, в которой можно выполнять стандартные арифметические операции и округлять действительные числа, все в постоянное время за операцию, то можно решить задачи, полные PSPACE, за полиномиальное время в этой модели. Но Рабин только округляет входные числа (с разным уровнем точности на разных итерациях), и эта ограниченная форма округления не вызывает проблем.
Дэвид Эппштейн
@SashoNikolov Я искал время наихудшего случая в , а также наихудший случай в вопросе 2. Это не имеет ничего общего с тем, является ли алгоритм детерминированным. Я не уверен, что произойдет, если вы объедините ожидаемое и амортизированное время. O ( 1 )o(nlogn) O(1)
Рафаэль