Znajdowanie maksymalnej odległości między (x, y) współrzędnymi

Question

Próbuję obliczyć maksymalną odległość manhattan dużego wejścia 2D, wejścia składają się z (x, y) s i co chcę zrobić, aby obliczyć maksymalną odległość między tymi współrzędnymi W czasie mniejszym niż O (n^2) mogę to zrobić w O (n^2), przechodząc przez wszystkie elementy takie jak:
* (Odległość Manhattan między dwoma punktami (X1, Y1) i (X2, Y2) jest: | X1-X2 | + | Y1-Y2 |)

for (0 -> n) 
    for (0-> n) 
     { // here i calculate |Xi - Xj| + |Yi - Yj| which is maximum } 

ale to nie będzie działać efektywnie w przypadku bardzo dużych nakładów :(
ktoś ma jakiś pomysł na lepsze algorytmu

?

Answer 1

Są tylko dwa przypadki do rozważenia, jeśli uwzględniamy tylko wyniki takie, że Xi <= Xj.

• Jeśli Yi <= Yj, to odległość jest (Xj + Yj) - (Xi + Yi)
• W przeciwnym przypadku odległość jest (Xj - Yj) - (Xi - Yi)

Przez złamanie go w tych przypadkach, mam pozbyć funkcji wartości bezwzględnej co znacznie ułatwia uzasadnić dystanse.

Po prostu wybieramy punkty o minimalnej i maksymalnej wartości x+y i obliczamy odległość. Następnie wybierz punkty z minimum i maksimum x-y i obliczyć odległość. Jedna z tych dwóch odległości jest twoją maksymalną.

Można to zrobić w O(n), która jest asymptotycznie optymalna.

Answer 2

Maksymalna odległość będzie między najbardziej odległymi od siebie punktami. Po prostu znajdziesz kropkę z maksymalną liczbą X i maksymalną Y, a następnie znajdź kropkę z minimum X i minimum Y i oblicz odległość między nimi. Nie może być wiele punktów, które będą spełniali kryteria .. ale przynajmniej yu'll mają znacznie mniejszą ilość punktów do sprawdzenia

Answer 3

pierwsza duża poprawa będzie:

for (X: 0 -> n) 
    for (Y: X -> n) 
     { compute the distance between X and Y } 

od odległości między X i Y jest taki sam, jak odległość między Y i X., która obniżyłaby twoje obliczenia o połowę ...

Answer 4

Jest to dość proste i może być obliczona w O(n)

Niech x1>x2 i y1>y2

max(|x1-x2|+|y1-y2|) = max(x1-x2+y1-y2) = max(x1+y1) - min(x2+y2) 

Niech x1>x2 i y1<y2

max(|x1-x2|+|y1-y2|) = max(x1-x2-y1+y2) = max(x1-y1) - min(x2-y2) 

Teraz zmień X1 X2 i podjąć takie same wyniki.

Ogólnie więc rozwiązanie jest

max ((max(xi+yi)-min(xi+yi)), (max(xi-yi) - min(xi-yi))) 

Answer 5

Najlepszą rzeczą do zrobienia z pytaniami jak to starają się ustalić kilka małych wyników, które pomogą Ci z całego problemu.

Na przykład, nie jest trudno określić, dla któregokolwiek z trzech punktów, A, B i C, które mają warunek, że B wynosi między (więcej o tym za chwilę) A i C, B będą nigdy nie należy oddalać się od czwartego punktu D niż jeden z A i C. Przy standardowej metryce odległości euklidesowej punkt znajduje się między dwoma innymi punktami, jeśli leży na łączącym je segmencie. W przypadku pomiarów Manhattan nie jest to takie proste - częściowo dlatego, że pojęcie segmentu nie jest tak dobrze zrozumiałe.

Bardziej ogólnym sposobem opisywania "między" jest (używając zapisu, że odległość od A do B wynosi | AB |): Punkt B znajduje się między dwoma punktami A, C, jeśli | AB | + | BC | = | AC |

Można zobaczyć, że odległość euklidesowa oznacza to, że B znajduje się na odcinku łączenia A i C.

w odległości Manhattan, oznacza to, że punkt B jest zawarte w prostokącie określonym przez A i C (co oczywiście może być prosty odcinek, jeśli AC jest równoległy do ​​jednej osi).

Wynik ten oznacza, że ​​dla dowolnego punktu, jeśli leży pomiędzy dwoma istniejącymi punktami, nie może być dalej od nowych punktów dodanych do zestawu niż dwóch, które go otaczają.

Ta informacja nie rozwiązuje problemu, ale pozwala odrzucić wiele potencjalnych przyszłych obliczeń. Po ustaleniu, że punkt znajduje się między dwoma innymi, nie ma sensu go śledzić.

Można więc rozwiązać ten problem, śledząc tylko najbardziej odległe punkty i ignorując wszelkie przypadki.

Ciekawym ćwiczeniem dla przypadkowego obserwatora

udowodnić, że można mieć nie więcej niż 4 różne punkty takie, że żaden z tych punktów są między dwoma innymi, w tym sensie, Manhattan.

Dzięki temu drugiemu wynikowi staje się jasne, że będziesz musiał tylko śledzić do 4 punktów.

Niektóre z innych metod, które już przedstawiono, są prawdopodobnie szybsze, ale w ten sposób są bardziej zabawne!

Extra Credit

uogólnić te pomysły n wymiarach