Per 3 punti in 2D:Minimizzare distanza massima di Manhattan di un punto ad un insieme di punti
P1(x1,y1),
P2(x2,y2),
P3(x3,y3)
ho bisogno di trovare un punto P(x,y), in modo tale che la massima delle distanze di Manhattan
max(dist(P,P1),
dist(P,P2),
dist(P,P3))
sarà minimo.
Qualche idea sull'algoritmo?
Preferirei davvero un algoritmo esatto.
Esiste un algoritmo esatto e noniterativo per il problema; come ha sottolineato Knoothe, the Manhattan distance is rotationally equivalent to the Chebyshev distance, e P è banalmente calcolabile per la distanza Chebyshev come media delle coordinate estreme.
I punti raggiungibili da P all'interno della distanza di Manhattan x formano un diamante intorno P. Pertanto, occorre trovare il diamante minimo che racchiude tutti i punti, e il suo centro sarà P.
Se si ruota la coordinata sistema di 45 gradi, il diamante è un quadrato. Pertanto, il problema può essere ridotto alla ricerca del più piccolo quadrato di chiusura dei punti.
Il centro di un quadrato più piccolo racchiude il centro del rettangolo di chiusura più piccolo (che è banalmente calcolato come il massimo e il minimo delle coordinate). Esiste un numero infinito di quadrati di chiusura più piccoli, poiché è possibile spostare il centro lungo il bordo più corto del rettangolo minimo e mantenere comunque un quadrato di chiusura minimo. Per i nostri scopi, possiamo semplicemente usare quello il cui centro coincide con il rettangolo che lo racchiude.
Così, in forma algoritmica:
Quindi x_c e y_c indicano le coordinate di P.
Se una soluzione approssimativa è corretta, è possibile provare un semplice algoritmo di ottimizzazione. Ecco un esempio, in Python
import random
def opt(*points):
best, dist = (0, 0), 99999999
for i in range(10000):
new = best[0] + random.gauss(0, .5), best[1] + random.gauss(0, .5)
dist_new = max(abs(new[0] - qx) + abs(new[1] - qy) for qx, qy in points)
if dist_new < dist:
best, dist = new, dist_new
print new, dist_new
return best, dist
Spiegazione: Si comincia con il punto (0, 0), o in qualsiasi altro punto casuale, e modificarlo qualche migliaio di volte, ogni volta mantenendo il meglio del nuovo e la in precedenza il punto migliore. A poco a poco, questo approssimerà l'optimum.
Nota che semplicemente prendendo la media o la mediana dei tre punti, o risolvendo per x ed y funziona indipendentemente non lavoro quando minimizzi il massima distanza di Manhattan. Counter-example: considera i punti (0,0), (0,20) e (10,10), o (0,0), (0,1) e (0,100). Se prendiamo la media dei punti più separati, questo darebbe (10,5) per il primo esempio, e se prendiamo la mediana questo sarebbe (0,1) per il secondo esempio, che hanno entrambi un massimo massimo distanza manhattan rispetto all'ottimo.
Aggiornamento: Sembra risolvendo per x e y in modo indipendente e prendendo la media dei punti più distanti fa nel lavoro fatto, a condizione che si fa un po 'di pre- e post-elaborazione, come sottolineato da thiton.
+1 per l'idea. Mi ricorda di corsi di analisi numerica di laurea. –
Alcuni punti non andranno persi, poiché la rotazione di 45 gradi produce un numero piuttosto elevato di numeri non interi? – nhahtdh
Quindi è solo (1) ruotare di 45 ° e (2) _quindi_ prendere la media dei punti più distanti, separatamente per xey y e (3) tornare indietro? Ancora non riesco a credere che sia così semplice, ma non riesca a trovare un difetto ... +1 –
@nhahtdh: Non farlo in aritmetica intera. Se si desidera ottenere un risultato intero, arrotondare il risultato. – thiton