У меня есть список 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

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

Этот подход имеет сложность времени выполнения , где 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).

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

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

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