Блог

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

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

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

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

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

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

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