Ближайшая группа из 3 баллов - PullRequest
Новая
       42

Ближайшая группа из 3 баллов

20 голосов
/ 24 сентября 2011

Существует ли известный эффективный алгоритм для нахождения ближайшей группы трех точек в облаке?

Это похоже на проблему ближайшей пары точек но я ищу три точки вместо двух.

Редактировать
Определение «ближайшего» повлияет на сложность алгоритма.Как указал Джек , нахождение минимального площади треугольника составляет 3 суммы и в любом случае не очень подходит для моего приложения.

Я надеюсь, что есть ещеэффективный алгоритм для нахождения минимального периметра (т.е. | AB | + | AC | + | BC |) или чего-то подобного (например, минимальный | AB | ² + | AC | ² + | BC | ².)Я не знаю причин, по которым это должно быть на 3 суммы сложнее, так как наличие трех коллинеарных точек в другом месте не повлияет на результат.

Примечание: мои точки имеют восемь измерений, поэтому любой алгоритм, который ограниченменьше размеров не подходит.

Ответы [ 4 ]

5 голосов
/ 30 сентября 2011

Эта проблема аналогична классической задаче нахождения ближайшей пары по набору точек.Вы можете адаптировать алгоритмы наихудшего случая O (n log n) , которые решают проблему ближайшей пары, для решения этой проблемы.

Конкретная проблема была представлена ​​в конкурсе Google Code Jam.Вот резюме анализа:

Количество точек может быть довольно большим, поэтому нам нужен эффективный алгоритм.Мы можем решить эту проблему за O (n log n) время, используя разделяй и властвуй .Мы разделим множество точек по вертикальной линии на два набора одинакового размера.Теперь существует три случая для треугольника с минимальным периметром: его три точки могут быть либо полностью в левом, либо полностью в правом, либо могут использовать точки из каждой половины.

Далее:

«Чтобы найти минимальный периметр для третьего случая (если он меньше p)»:

  1. Мы выбираем точки, которые находятся на расстоянииp / 2 от вертикальной разделительной линии.
  2. Затем мы перебираем эти точки сверху вниз и поддерживаем список всех точек в блоке размером pxp / 2 с нижним краемв самой последней рассматриваемой точке.
  3. По мере добавления каждой точки в поле мы вычисляем периметр всех треугольников, используя эту точку и каждую пару точек в блоке.(Мы могли бы исключить треугольники полностью слева или справа от разделительной линии, поскольку они уже были рассмотрены.)

Мы можем доказать, что количество точек в квадрате не более16, поэтому нам нужно учитывать не более одного небольшого постоянного числа треугольников для каждой точки.

Мне кажется, вы могли бы даже адаптировать метод для работы в | AB | ² + | AC| ² + | BC | ² кейс.

3 голосов
/ 30 сентября 2011

Существует очевидный алгоритм, который работает в O(n^2).

1) выполнить триангуляцию Делоне - O(n log n), чтобы мы получили планарный график.

Поскольку именно триангуляция Делоне максимизирует минимальный угол, ясно, что ближайшие 3 точки должны быть связаны как минимум двумя ребрами (но они не обязательно должны образовывать треугольник!). В противном случае было бы больше более близких точек или более закрытых углов.

2) для каждой точки (вершины графа) мы исследуем каждую пару смежных ребер и смотрим 3 вершины, определенные этими двумя ребрами.

Сколько времени займет шаг 2)? Так как график плоский, число ребер составляет <= 3n - 6, то есть <code>O(n). Таким образом, этот шаг займет O(n^2) в худшем случае (O(n) в типичном случае, когда степень каждой вершины ограничена).

Таким образом, весь алгоритм равен O(n^2). Обратите внимание, что шаг 2) является каким-то наивным (грубым) решением, поэтому я думаю, что есть место для улучшений (также шаги 1 и 2, вероятно, можно объединить).

0 голосов
/ 29 сентября 2011

Это специфическая форма проблемы k-ближайшего соседа , а именно, где k = 3. На приведенной странице не указывается алгоритмическая сложность, но совершенно очевидно, что наивный подход заключается в вычислении расстояния от выбранной точки до всех других точек, а затем вычислении расстояния от этой точки до всех других точек, а также расстояния наша исходная точка для новой выбранной точки O (n k-1 ). Рассмотрим псевдокод: 

for pointB in searchSpace do:
    distanceAB := calculateDistance(pointA, pointB)
    for pointC in {searchSpace} - {pointB} do:
        distanceBC := calculateDistance(pointB, pointC)
        distanceCA := calculateDistance(pointC, pointA)
        if (distanceAB + distanceBC + distanceCA) < currentMin then:
            currentMin := distanceAB + distanceBC + distanceCA
            closestPoints := {pointA, pointB, pointC}

Обратите внимание, что мы предполагаем, что pointA уже удален из searchSpace. Это алгоритм O (n 2 ). Предполагая, что размерность относительно мала, или что функция calculateDistance растет линейно или меньше вместе с размером, это дает решение в приемлемых временных рамках. Оптимизация, конечно, может быть, но она может и не потребоваться.

Если вы хотите увидеть настоящий код, в Википедии есть много ссылок на реализации .

0 голосов
/ 24 сентября 2011

Упомянутая вами проблема - это сложная проблема 3sum. Посмотрите на http://www.cs.mcgill.ca/~jking/papers/3sumhard.pdf для деталей.

Эта проблема также может быть выражена как нахождение наименьшего треугольника из заданных точек.

EDIT:

По сути, сложная задача 3sum означает, что нижняя граница равна O (n ^ 2). Там и там может быть небольшое улучшение, но ничего особенного не поделаешь.

Об этой конкретной проблеме (наименьший треугольник) см. Главу 3 http://www.cs.princeton.edu/~chazelle/pubs/PowerDuality.pdf.

...