Эффективная длинная арифметическая прогрессия для набора линейных точек

Question

Самая длинная арифметическая прогрессия набора чисел {ab ₁ , ab ₂ , ab ₃ .... ab _n } определяется как подмножество {bb ₁ , bb ₂ , bb ₃ .... bb _n }, такое что b _{i + 1} - b _i постоянно.

Я хотел бы распространить эту задачу на набор двумерных точек, лежащих на прямой линии.Определим Dist (P ₁ , P ₂ ) - расстояние между двумя точками P ₁ (X ₁ , Y ₁ ) и P ₂ (X ₂ , Y ₂ ) на линии как

Dist (P ₁, P ₂ ) = Dist ((X ₁ , Y ₁ ), (X ₂ , Y ₂ )) = (X ₂ - X ₁ ) ² + (Y ₂ - Y ₁ )) ²

Теперь Для заданного набора точек мне нужно найти наибольшую арифметическую прогрессию такую, что Dist (P _i , P _{i+ 1} ) является константой, если предположить, что все они лежат на одной строке (константы m & C).

Я немного исследовал, но не смог выяснить алгоритм, который лучше, чем O (n ² ).

На самом деле в настоящее время я веду словарь:

DistDict=dict()

и говорю, что точки определены в списке как

Points = [(X1,Y1),(X2,Y2),....]

тогда это то, что я делаю

for i,pi in enumerate(Points):
    for pj in Points[i+1:]:
         DistDict.setdefault(dist(pi,pj),set([])).add((pi,pj))

, так что все, что я закончил, получило словарь точек wкоторые находятся на одинаковом расстоянии.Поэтому единственное, что мне нужно сделать, - это просмотреть, чтобы найти самые длинные set.

Мне просто интересно, что это должно иметь лучшее решение, но почему-то я не могу найти одно.Я также видел пару похожих постов SO, но я не могу найти что-то более эффективное, чем O (n ² ).Является ли это каким-то образом трудной проблемой NP, что у нас никогда не может быть чего-то лучшего, или, если нет, какой подход может быть принят.Обратите внимание, что я наткнулся на сообщение, в котором говорится об эффективном алгоритме «разделяй и властвуй» , но не смог сделать из этого ни головы, ни хвоста.

Любая помощь в этом отношении?

Примечание *** Я помечаю этот Python, потому что я понимаю Python лучше, чем, возможно, Matlab или Ruby.C / C ++ / Java тоже хорошо, так как я тоже немного разбираюсь в них: -)

Answer 1

Во-первых, ваше определение расстояния неверно.Вы должны взять квадратный корень.Во-вторых, если вы знаете, что все точки лежат на прямой линии, вы можете просто игнорировать координаты y (если линия не вертикальная) или координаты x (если линия не горизонтальная).Тогда это сводится к проблеме в вашем первом абзаце.

Answer 2

Подводя итог: как указывал @TonyK, если вы предполагаете, что точки лежат на прямой линии, вы можете свести ее к одномерному случаю, который уже подробно обсуждался здесь .В решении используются быстрые преобразования Фурье, как упомянуто @ YochaiTimmer.

Дополнительное примечание: Проблема почти наверняка не является NP-трудной, поскольку она имеет эффективное решение O (n log n), поэтому подразумевается P = NP..

Answer 3

Вы можете изучить Быстрое преобразование Фурье методы для умножения .O (N log N)

Вы могли бы сделатьчто-то похожее с твоей проблемой.