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

У меня есть список L точек (x, y) и обычная евклидова дистанционная мера

enter image description here

Как найти максимальное расстояние, указанное двумя точками в этом списке? Или, более формально: Как найти

enter image description here

Тривиальный подход

Самый простой способ решить эту проблему - попробовать все:

def find_max_dist(L):
    max_dist = d(L[0], L[1])
    for i in range(0, len(L)-1):
        for j in range(i+1, len(L):
            max_dist = max(d(L[i], L[j]), max_dist)
    return max_dist

Чтобы сделать вычисления быстрее, я могу использовать квадрат расстояния в циклах и вернуть корень в конце.

Этот подход имеет сложность времени выполнения O(n^2), где n - это длина списка L. (И постоянная сложность пространства).

Выпуклая оболочка

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

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

def find_max_dist_graham_triv(L):
    H = Graham_scan(L)
    return find_max_dist(L)

Теперь это точка, где я не уверен. Я думаю, что можно улучшить это так:

def find_max_dist_graham_c1(L):
    H = Graham_scan(L)  # Get ordered list of convex hull points
    max_dist = d(L[0], L[1])
    for i in range(0, len(L)-1):
        loop_max_dist = 0
        for j in range(i+1, len(L):
            curr_dist = d(L[i], L[j])
            if curr_dist < loop_max_dist:
                break
            loop_max_dist = curr_dist
            max_dist = max(loop_max_dist, max_dist)

    return max_dist

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

Интуитивно я продолжу улучшать алгоритм: как только первый внутренний цикл заканчивается, мы обнаружили "самую длинную диагональ" этого цикла. Эта диагональ отделяет все остальные точки корпуса в двух дизъюнктных множествах. Каждая более длинная диагональ должна состоять из точек из обоих этих множеств (правильно?):

def find_max_dist_graham_c1(L):
    H = Graham_scan(L)  # Get ordered list of convex hull points
    max_dist = d(L[0], L[1])  # Get a fist idea what the longest distance might be

    i = 0
    p1 = L[i]  # Grab a random point
    loop_max_dist = 0
    for j in range(1, len(L):
        curr_dist = d(L[i], L[j])
        if curr_dist < loop_max_dist:
            break
        loop_max_dist = curr_dist
        max_dist = max(loop_max_dist, max_dist)
    # Every diagonal that is longer than the best one found with L[0]
    # has to have points in both of the following two sets (correct?):
    # [1...j] and [j+1...len(L)]

    # Try to find a neighboring diagonal that is longer.
    change = True
    while change:
        change = False
        if d(L[i-1], L[j+1]) > max_dist:
            max_dist = d(L[i-1], L[j+1])
            i -= 1
            j += 1
            change = True
        elif d(L[i+1], L[j-1]) > max_dist:
            max_dist = d(L[i+1], L[j-1])
            i += 1
            j -= 1
            change = True
    return max_dist

Каждая точка P на выпуклой оболочке имеет точку Q на выпуклой оболочке такую, что PQ является самой длинной диагональю, включая P. Но тогда P также является "конечной точкой" для самой длинной диагонали Q?

Я действительно не уверен, правильный ли этот алгоритм. Это было бы в O (n log n).

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

Хотя у меня было много второстепенных вопросов, главный вопрос:

Что такое эффективный способ найти максимальное расстояние точек в списке точек?

Ответы

Ответ 1

Вы должны посмотреть на вращающиеся суппорты (http://en.wikipedia.org/wiki/Rotating_calipers) - они широко используются для таких проблем. Кроме того, ваше предположение неверно. Для фиксированной точки p на выпуклом многоугольнике: диагональ может сначала увеличиваться, затем уменьшаться, а затем увеличиваться, а затем снова уменьшаться. По крайней мере, у меня есть случай, когда это происходит.

Эвристический подход также: выберите точку x. Найдите более удаленную точку y. Найдите более удаленную точку z от y. d (z, y) является хорошей оценкой.

Изображение, которое иллюстрирует диагонали:

enter image description here

1- > 2: увеличение; 2- > 3 уменьшается; 3- > 4; 4- > 5 убывает. Этот рисунок может быть не точным, переместите точки, которые 3 и 4 указывают на немного дальше от p (в одной строке).

Ответ 2

Предполагая, что у вас есть равномерное распределение точек, вы можете сделать следующее:

Найти max_x и min_x как максимальную и минимальную координаты X - (O(n)). Это значение должно помочь вам выбрать константу k как "лучшую" для текущего набора точек. Различное значение k будет влиять только на сложность алгоритма.

Рассмотрим новую структуру данных, которая является матрицей как и является вектором векторов или векторов связанных списков, позволяет назвать ее structure, где structure[i] - соответствующие векторные/связанные списки (как описано выше). Заполните эту структуру данных следующим образом: structure[i] должен содержать точки, у которых их координата x находится в диапазоне [max_x+ik,max_x+(i+1)k], это займет другое время O(n) и O(n) дополнительное пространство. Теперь вы сортируете каждую запись structure[i] по координате y. Сделав это, достаточно вычислить расстояния (грубую силу) между следующим набором точек: structure[0], structure[structure.length()-1], крайности (запись в первом и последнем индексе) всех остальных structure[i].

В основном это почти то же самое, что и для выпуклой оболочки и для вычисления расстояний точек, находящихся на корпусе, разница в том, что выбор правильного k может сделать его быстрее или медленнее. Имея худшую сложность O(n^2) и лучшую сложность случая O(nLg(n)). Где k будет влиять на торговлю либо сортировкой больших групп точек, либо с большим количеством точек для вычисления расстояний между ними.

Ответ 3

Максимальное расстояние точек в E2 и E3 для наборов данных LARGE

Для больших наборов данных даже O (N lgN) высока, migt может быть полезен для просмотра

Scala