Odległość mięzy punktami w metryce miejskiej

Witam, mam za zadanie znaleźć na układzie współrzędnych punkt optymalny (suma odległości do innych punktów w metryce miejskiej ma być najmniejsza). Rozumiem że robi się to tak: bierze x współrzędne punktów ze zbioru i wybiera medianę. Analogicznie dla współrzędnych y. Z tym, że w zadaniu jest dodana jedna rzecz, która komplikuje mi sprawę.

"Odległość między punktami to większy z modułów różnicy współrzędnych x i y"

No właśnie i tu powstaje problem bo dla punktów

(2, 12)
(1, 2)
(0, 10)
(1, 2)
(6, 8)

Gdyby liczone było to w sposób normalny to punkt optymalny wychodzi mi (1, 8) Wiem, że odpowiedź dla takiego przykładu to (4,6)
Algorytm ma działać w liniowo co do ilości punktów, czyli do wyznaczenia mediany będę musiał użyć pewnie algorytmu magicznych piątek. No ale to później teraz problem przysparza mi ten dziwny sposób liczenia odległości.

Dzięki z góry za pomoc;)

W czym problem?
Dla pierwszego punktu to: max(abs(2-x),abs(12-y))
Musisz znaleźć takie x,y aby suma tych maxów była minimalna.

Z tego malo precyzyjnego opisu metryki wnioskuje, ze chodzi o metryke Czebyszewa (L-inf).
Na wiki mozna znalezc, ze TO jest punktem optymalnym przy L-inf.

Do tamtego przykładu poprawna odpowiedź jest na pewno poprawna. A z jeśli o większy z modułów to wiem co to jest tylko nie potrafię przez to policzyć zadania. Gdyby nie było tego warunku to wtedy liczę to w ten sposób:
oznaczam na osi x punkty {0, 1, 1, 2 , 6} i wybieram środkowy, a następnie na osi y punkty {2, 2, 8, 10, 12} i również wybieram środkowy co daje mi punkt (1, 8).
Podając to do tego wzoru max(abs(2-x),abs(12-y)) nie wiem jak wyznaczyć x i y trzymając się złożoności liniowej...

porschelukas napisał(a):

Odległość między punktami to większy z modułów różnicy współrzędnych x i y
Jak @0x200x20 słusznie zauważył jest to metryka maksimum (Czebyszewa, L-inf).

Jeśli są to punkty dwuwymiarowe to można skorzystać z pewnej bardzo fajnej własności. Jeśli obrócimy układ współrzędnych o 45° to przy odpowiednim przeskalowaniu metryka pokryje się z metryką miasto (L-1) (zob. rysunki na http://pl.wikipedia.org/wiki/Odleg%C5%82o%C5%9B%C4%87_Minkowskiego). Jako że wyznaczamy średnią z tych punktów skala tu nie ma znaczenia. Tak więc:

1. Obróć współrzędne o 45° stopni (można też skalować, nie wpłynie to na wynik)
2. Wyznacz średnią w metryce miasto
3. Obróć wynik o -45° stopni (a dokładnie wykonaj przekształcenie odwrotne do tego w pkt. 1)

Ad. 1 i 3 Robi się to bardzo prosto.

• obrót o 45° (wraz z pewnym skalowaniem, ale ono jest nieistotne)
  x' = x - y
  y' = x + y
• z powrotem:
  x = (x' + y') / 2
  y = (y' - x') / 2

Ad.2
Musimy znaleźć punkt centralny (centroid) w metryce miasto. Musimy znaleźć taki punkt, którego suma odległości "x-owych" i suma odległości "y-owych" są najmniejsze. Tu trzeba zauważyć, że jedne nie wpływa na drugie - punkt ten możemy sobie dowolnie przesuwać wzdłuż osi X a sumaryczna odległość "y-owa" się nie będzie zmieniać (i vice-versa). Zatem zadanie jest banale - wyznaczamy średnią arytmetyczną medianę współrzędnych "x-owych" oraz średnią arytmetyczną medianę współrzędnych "y-owych" i to jest nasz punkt centralny. Nie zapomnij obrócić wyniku (krok 3)!

Macie racje - mid range minimalizuje troszke cos innego.

Wyznacz średnią w metryce miasto

Przyczepie sie tylko, ze centroid w L1 to nie jest srednia arytmetyczna ze wspolrzednych a mediana.