Расстояние Фреше в O (n)

Question

В ряде статей я видел, что алгоритм Fréchet сложность O(n^2).
, что пути представлены в виде массивов Q и P, размером nкаждый

Что, если я начну с Q[0], P[0] и проверю все возможности и выберу минимальное:

STP_i,j = min(|Q[i] - P[j+1]|, |Q[i+1] - P[j+1]|,|Q[i+1] - P[j]|)

И соответственно изменим i и j.
Так что я могу получить ответ на O (n).

Я ошибаюсь?

Answer 1

Рассмотрим следующий пример:

Возьмите точки, отмеченные черным, как начало линий.На первом этапе ваш алгоритм продвинется на одну точку в обеих строках.Тем не менее, расстояние Фреше в этом случае будет расстоянием между первой красной точкой и третьей синей точкой, но, поскольку ваш алгоритм уже отошел от первой точки, он даст вам большее значение.