Największa Odległość

Witam.
Mój problem przedstawia się tak. Na wejściu dostaję n punktów które są współrzędnymi w 2wymiarowej przestrzeni xy. Muszę wyznaczyć największą odległość pomiędzy dwoma punktami z zadanego zbioru w możliwie najlepszej złożoności. Ktoś wie jak to zrobić, albo chociaż jest w stanie polecić jakąś lekturkę na ten temat?:)

Będziesz musiał spawdzić wszystkie pary punktów i znaleźć tę, dla której odległość jest maksymalna (nic innego nie przychodzi mi teraz do głowy). Jednak żeby zminimalizować liczbę punktów wyznacz najpierw zbiór punktów, które tworzą wielokąt wypukły, do którego należą wszystkie pozostałe punkty. Maksymalnej odłegłości szukaj wśród wierzchołków tego wielokąta.

O tym wielokącie możesz poczytać tu http://en.wikipedia.org/wiki/Convex_hull

myślę, że jakbyć zmodyfikował odrobinę to: http://wazniak.mimuw.edu.pl/index.php?title=Zaawansowane_algorytmy_i_struktury_danych/Wyk%C5%82ad_12#Najmniej_odleg.C5.82a_para_punkt.C3.B3w
to osiągnąłbyś zamierzony efekt

ktoś tutaj odpowiedział na Twoje pytanie:
Czy slyszal ktos o takim algorytmie??

ja bym zrobił tak:
#wyszukał 4 punkty każdy mający ekstremalną współrzędną (złożoność o(n)) max_x max_y min_x min_y
#z tych 4 punktów wyznaczył najodleglejszą parę (6 testów odległości) (w sumie do tego momentu to jest optymalizacja bo można zacząć od dowolnej pary)
#ta para wyznacza mi dwa okręgi o jednym promieniu równym ich odległości i środkach wyznaczonych przez te punkty.
#szukam punktów, które są poza jednym z okręgów (złożoność o(n)) jeśli się taki znalazł aktualizuje promień okręgów (i środek drugiego)
#szukam punktów, które są poza drugim okręgiem (złożoność o(n)) jeśli się taki znalazł aktualizuje promień okręgu
całość ma złożoność o(n) i jest bardo prosta w implementacji

@MarekR22, niestety pomysł nie wypali:
<image></image>

wiedziałem, ze powinienem się trzymać pierwotnego pomysłu :/.
Pierwotny pomysł polegał na tym, że każda para punktów wyznacza średnicę okręgu testowego.
To co znajdzie się wewnątrz takiego okręgu jest odrzucane do kolejnych testów. Z tego powinno wyjść o(n log(n)), bo jeśli coś jest poza tym okręgiem to jeszcze nie uaktualnia okręgu.
Jeszcze nad tym pomyślę, tym razem bez pośpiechu :).

@_13th_Dragon +1 za fajny test case.

Tzn. znaleźć największą odległość między dwoma punktami w zbiorze?

Najpierw znajdujesz otoczkę wypukłą Θ(n log n)
Teraz - w teorii - dla każdej ściany wierzchołka tworzysz prostą i wyznaczasz prostą równoległą do niej i styczną do wielokąta:

Jeśli najodleglejsza para punktów zawiera punkt styczności to wiadomo że będzie on jednym z punktów testowanej ściany wielokąta.
Jako że idziesz ścianami po kolei, wystarczy zapamiętać który punkt był ostatnio styczny i testować następujące po nim - złożoność Θ(n).

Już samo to jest dość proste do napisania, ale z tego co pamiętam można (opierając się technicznie na tym pomyśle) jeszcze prościej - trzymasz dwa punkty - jeden 'iterator' i drugi najodleglejszy od niego w otoczce wypukłej. Kiedy przesuwasz 'iterator' do następnego, przesuwasz drugi tak długo dopóki powoduje to zwiększenie odległości między tymi punktami (bo na pewno jeśli masz dwa najodleglejsze punkty w wielokącie wypukłym i przesuniesz jeden w, powiedzmy, lewo a drugi w prawo to odległość się nie zwiększy). Czyli w zasadzie kilkulinijkowiec, złożoność Θ(n).