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

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

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

Edit
Определение "ближайшего" будет влиять на сложность алгоритма. Как отметил Jack, поиск минимального треугольника области 3sum-hard и в любом случае не очень подходит для моего приложения.

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

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

Ответы

Ответ 1

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

1) выполните треугольник Delaunay - O(n log n), поэтому мы получаем плоский график.

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

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

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

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

Ответ 2

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

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

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

В дальнейшем:

"Найти минимальный периметр для третьего случая (если он меньше р)":

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

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

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

Ответ 3

Проблема, о которой вы упомянули, - это проблема проблемы 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.

Ответ 4

Это конкретный вид проблемы 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 растет линейно или меньше с размерностью, это дает решение в приличном временном ограничении. Оптимизации, безусловно, можно было бы сделать, но они могут не потребоваться.

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