Najbardziej oddalone punkty

Question

Siemka ponownie. Mam zadanie, w którym trzeba znaleźć parę najbardziej oddalonych punktów. Wiem tyle, że punkty te zawsze leżeć będą na otoczce wypukłej. Mam już algorytm tworzący taką otoczkę w O(n*log(n)), ale nie wiem jak wydajnie znaleźć taką parę oprócz przeszukiwania wszystkich par w O(n^2).

Jakieś pomysły?

Answer 1

Mój pierwszy pomysł był taki, żeby zrobić gąsienice. Dla p1 znajdujemy najbardziej oddalony punkt, powiedzmy q1. Potem bierzemy p2 (kolejny punkt z otoczki) i bierzemy kolejne punkty z otoczki na prawo od q1 (nazwijmy je q2) dopóki dist(p2, q2) będzie niemalejące. Ten algorytm ma małe problemy gdy otoczka przypomina owal.

Znalazłem natomiast algorytm Shamos, który działa na podobnej zasadzie. Idea jest taka, żeby toczyć tę otoczkę jak głaz. Kładziemy otoczke na odcinku (p_1, p_n) (gdzie n to liczba punktów na otoczce) i szukamy punktu, który znajduje się najwyżej. Potem przetaczamy otoczkę na odcinek (p2, p1) i znowu szukamy najwyższego punktu, przetaczamy na (p3, p2) itd.

W końcu któryś z punktów z odcinka na którym leżała otoczka i ten najwyższy punkt będą tworzyły parę najbardziej oddalonych punktów.

Pseudokod

Wizualizacja

Comments

dobra, ale jak znaleźć najwyższy punkt otoczki, gdy stoi ona np. bokiem, albo pod innym nachyleniem niż pierwotnie?

Podam przykład, mamy taki zestaw punktów wraz z otoczką:

No i tak jak powiedziałeś, przewracam na początku na bok o punktach p_1 oraz p_n mojej otoczki. Tyle, że jak mam wiedzieć, że w przypadku poniżej najwyżej stoi 4 oraz którą parę sprawdzać (mam na myśli aktualizację max odległości)? p_1 <-> p_4 czy może p_6 <-> p_4 ?

---

Jak spojrzysz na pseudokod to tam jest szukane największe pole trójkąta, w którym jeden odcinek to ten na którym leży otoczka. Wtedy oczywiście pole będzie największe, gdy punkt będzie najwyżej. Jeśli chodzi o to którą parę punktów sprawdzać to nie wiem. Zawsze można sprawdzić obydwie