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

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

введите описание изображения здесь

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

введите описание изображения здесь

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

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

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) и сканирование Грэма, кажется, делает это. Но после нахождения сложного корпуса мне все равно нужно пройти максимальное расстояние. Так что я бы в конечном итоге

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).

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

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

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

Источник

3 ответа

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

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

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

введите описание изображения здесь

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

Источник

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

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

Источник

Максимальное расстояние между точками в E2 и E3 для БОЛЬШИХ наборов данных

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

Skala

Источник
Другие вопросы по тегам