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?:)
- Rejestracja:ponad 12 lat
- Ostatnio:prawie 12 lat
- Postów:8
1
- Rejestracja:prawie 15 lat
- Ostatnio:prawie 12 lat
0
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
- Rejestracja:prawie 16 lat
- Ostatnio:5 miesięcy
- Postów:2514
0
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??
edytowany 1x, ostatnio: krwq
- Rejestracja:około 17 lat
- Ostatnio:3 minuty
0
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
edytowany 3x, ostatnio: MarekR22
- Rejestracja:ponad 19 lat
- Ostatnio:2 miesiące
1
</image>
edytowany 1x, ostatnio: _13th_Dragon
- Rejestracja:około 17 lat
- Ostatnio:3 minuty
0
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.
edytowany 1x, ostatnio: MarekR22
- Rejestracja:prawie 16 lat
- Ostatnio:4 miesiące
0
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).
edytowany 2x, ostatnio: msm
Zobacz pozostałe 7 komentarzy
msm
@_13th_Dragon - chyba po co używać tablic skoro 'ma taką samą złożoność (czytania) jak mapa, czyli O(1)' a nie można wstawiać do środka ;P. @krwq - to zależy czy jesteś praktykiem czy teoretykiem ;). Tak, w praktyce często (ale nie zawsze) algorytmy Θ(n log n) zachowują się podobnie albo nawet lepiej niż Θ(n). Ale jeśli chodzi o teorię złożoności obliczeniowej to różnica jest olbrzymia ;]
msm
(btw. równoważność klas złożoności jest precyzyjnie zdefiniowana i tutaj również log n ma się nijak do 1)
krwq
przy mapach masz dużo gorszą stałą niż w tablicy :P praktykiem jestem :D
_13th_Dragon
@msm, mówimy nie o log(n) tylko o log(log(n)). @krwq - fakt że w stl mapy są skopane - niczego nie dowodzi.
krwq
np. różnicę w O(n log n) w secie a O(n log n) w funkcji sort na vectorze da się wyraźnie odczuć, a niby ta sama złożoność