[Algorytmy] Dwa najbardziej oddalone od siebie punkty

[adambak]

Mam taki problem: danych jest \(\displaystyle{ n}\) punktów. Ponumerujmy je od \(\displaystyle{ 0}\) do \(\displaystyle{ n-1}\). Trzeba znaleźć taką parę punktów: \(\displaystyle{ (x_{i} ; \ y_{i})}\) oraz \(\displaystyle{ (x_{j}; \ y_{j})}\), dla których wartość: \(\displaystyle{ s=\left|x_{i}-x_{j} \right|+\left|y_{i}-y_{j} \right|}\) jest największa i oczywiście obliczyć tę wartość. Nie mogę wpaść na nic lepszego niż \(\displaystyle{ O(n^{2})}\). Jakaś wskazówka do czegokolwiek bardziej optymalnego?

[argv]

Wskazówka: otoczka wypukła.

[adambak]

a nie będzie to trochę przerost formy nad treścią? potem trzeba by badać punkty należące do otoczki, mogło by to wcale nie przyspieszyć.. z resztą wzorcowe rozwiązanie tego problemu to \(\displaystyle{ O(n)}\) (strasznie szybko, dla mnie to szok)..

[argv]

Otoczke Grahamem \(\displaystyle{ O(nlogn)}\). Otoczka wypukła o n punktach ma n par punktów antypodycznych -. Można wyznaczać te pary punktów antypodycznych (liniowo się da) i wziąć tę parę o największej odległości więc wciąż \(\displaystyle{ O(nlogn)}\).
Co do \(\displaystyle{ O(n)}\) to uważam że bez dodatkowych założeń się nie da

[adambak]

ok, dziękuję, zmotywuje mnie to wreszcie do porządnego napisania algorytmu na znajdowanie otoczki i przyswojenie go.. żeby się zmieścić w limicie czasu to najwyżej napiszę szybkie wczytywanie punktów jakimś fgetc_unlocked(stdin); albo coś pozdrawiam

[PMichalak]

Argv, chyba dokładnie nie przeczytałeś treści, chodzi tutaj o metrykę miejską, nie euklidesową... a otoczka w takiej metryce to po prostu najmniejszy prostokąt zawierający te punkty. Spróbuj wybrać wszystkie punkty, które są na brzegu tego prostokąta ( czas \(\displaystyle{ O(n)}\) ), a następnie odpal gąsienice. Na pierwszy rzut oka powinno działać.

[Zordon]

Wskazówka: otoczka wypukła.

To rozwiązanie działa bez problemu gdy jest odległość Euklidesowa. Tutaj mam pewne wątpliwość czy w metryce manhattan też będzie ok. Pewnie tak, ale na pierwszy rzut oka nie widzę uzasadnienia. Dokładniej to czy takie liniowe skanowanie otoczki będzie dobre.

-- 12 czerwca 2011, 20:30 --

Argv, chyba dokładnie nie przeczytałeś treści, chodzi tutaj o metrykę miejską, nie euklidesową... a otoczka w takiej metryce to po prostu najmniejszy prostokąt zawierający te punkty. Spróbuj wybrać wszystkie punkty, które są na brzegu tego prostokąta ( czas \(\displaystyle{ O(n)}\) ), a następnie odpal gąsienice. Na pierwszy rzut oka powinno działać.

co to znaczy na brzegu prostokąta, jeśli chodzi o prostokat wyznaczony przez najdalsze punkty odpowiednio na lewo prawo, w gore i w dol to to zdecydowanie nie działa.
No chyba, że nie rozumiem "gąsienicy" ;d

[adambak]

a następnie odpal gąsienice.

nie rozumiem..


faktycznie, dużo ułatwia ta metryka miejska (Manhattan distance), już mi się zaczyna tlić w głowie rozwiązanie.. znajduję ten prostokąt co jest proste, jednak brakuje mi co potem, żeby ograniczyć liczbę operacji..

-- 12 cze 2011, o 21:38 --

co do sprawdzania tej odległości dla najbardziej skrajnych punktów (na brzegu prostokąta) to nie ma szans.. już to przerabiałem, przykład punktów:

\(\displaystyle{ (0;2)}\), \(\displaystyle{ (1;-1)}\), \(\displaystyle{ (4;-2)}\), \(\displaystyle{ (7;2)}\), \(\displaystyle{ (6;7)}\), \(\displaystyle{ (2;8)}\)


najbardziej oddalone wg opisanych zasad są: \(\displaystyle{ (1;-1)}\) i \(\displaystyle{ (6;7)}\) o ile się nie mylę, a są w środku prostokąta..

[argv]

Argv, chyba dokładnie nie przeczytałeś treści, chodzi tutaj o metrykę miejską, nie euklidesową

Racja - mój błąd

[abc666]

A czy przy takiej metryce nie musimy sprawdzić tylko 8 punktów, tych najbliżej rogów prostokąta, na każdym boku? Wybieramy te punkty w liniowym czasie jeszcze podczas wyboru tych które należą do brzegu a potem sprawdzamy w czasie stały.

[paladin]

Klasycznym trikiem jest obrócenie całej płaszczyzny o \(\displaystyle{ 45^\circ}\) - metryka miejska zmienia się wtedy w metrykę maksimum. Dla metryki maksimum to zadanie robi się łatwe...

[adambak]

A czy przy takiej metryce nie musimy sprawdzić tylko 8 punktów, tych najbliżej rogów prostokąta, na każdym boku? Wybieramy te punkty w liniowym czasie jeszcze podczas wyboru tych które należą do brzegu a potem sprawdzamy w czasie stały.

mógłbyś trochę rozwinąć? bo wydaje mi się że brzmi bardzo sensownie (czuję tutaj w powietrzu liniówkę).. co znaczy najbliżej rogów prostokąta, licząc odległość wg powyższej zasady?

[abc666]

Tylko czerwone punkty wchodzą w grę. Mogą się one w pewnych przypadkach pokrywać. Tutaj narysowałem sytuacje, że jest ich 8.

Uzasadnienie:
Załóżmy, że co najmniej jeden punkt z pary najdalszych jest niebieski. Teraz mamy takie przypadki:
-drugi punkt z pary leży na tym samym boku, ale wtedy mamy sprzeczność bo najbardziej oddalone punkty na boku są czerwone
-drugi punkt leży na przeciwległym boku, wtedy droga ma kształt litery L, najpierw do przeciwległego boku, potem do punktu, jednak ta droga będzie najdłuższa kiedy "drugie" ramie tego L będzie najdłuższe, a ma to miejsce wtedy kiedy wybierzemy dwa czerwone punkty
-drugi punkt leży na boku prostopadłym, analogicznie musimy przejść drogę w kształcie L, np. po bokach prostokąta i znowu najdalsza możliwa odległość jest miedzy czerwonymi

Może trochę chaotycznie to opisałem, ale analiza na obrazku odległości w rozważanej metryce powinna wyjaśnić ewentualne wątpliwości.

[adambak]

coś bym zmienił.. zobacz co wcześniej napisałem, para najdalszych punktów nie musi leżeć wcale na prostokącie:

co do sprawdzania tej odległości dla najbardziej skrajnych punktów (na brzegu prostokąta) to nie ma szans.. już to przerabiałem, przykład punktów:

\(\displaystyle{ (0;2)}\), \(\displaystyle{ (1;-1)}\), \(\displaystyle{ (4;-2)}\), \(\displaystyle{ (7;2)}\), \(\displaystyle{ (6;7)}\), \(\displaystyle{ (2;8)}\)

najbardziej oddalone wg opisanych zasad są: \(\displaystyle{ (1;-1)}\) i \(\displaystyle{ (6;7)}\) o ile się nie mylę, a są w środku prostokąta..

para najdalszych punktów nie leży na prostokącie, jednak podoba mi się pomysł wyszukiwania punktów najbliższych (licząc odległość wg wyżej wymienionej zasady) rogom prostokąta. nasz prostokąt w przykładzie jest ograniczony przez:
\(\displaystyle{ x=0}\)
\(\displaystyle{ x=7}\)
\(\displaystyle{ y=-2}\)
\(\displaystyle{ y=8}\)
a para najdalszych punktów kwalifikuje się do punktów położonych najbliżej rogów prostokąta.. ma sens?

[Zordon]

paladin podał eleganckie rozwiązanie, powiem tylko, że metryka maksimum to coś takiego: \(\displaystyle{ d((x_1,y_1),(x_2,y_2))=max(|x_1-x_2|,|y_1-y_2|)}\). Najlepiej widać to na rysunku.
W każdym razie chodzi teraz o to, żeby punkty przekształcić w ten sposób:
\(\displaystyle{ (x,y) \mapsto (x-y,x+y)}\) i szukać największej odległości w metryce maximum. Wynik to właśnie szukana wielkość