Distanza di Čebyšëv

$D_{Chess}(x,0)=1$

In matematica, la distanza di Čebyšëv, conosciuta anche come distanza della scacchiera o distanza di Lagrange, è una distanza su spazi vettoriali tale per cui la distanza tra due vettori è il valore massimo della loro differenza lungo gli assi. Si tratta di una versione finito-dimensionale della metrica uniforme.

Prende il nome dal matematico russo Pafnutij L'vovič Čebyšëv. Negli scacchi la distanza tra le celle in termini di mosse necessarie al re è data dalla distanza di Čebyšëv, da cui il nome.

Definizione

La distanza di Čebyšëv tra due punti $p$ e $q$ in uno spazio vettoriale, come ad esempio uno spazio euclideo, è definita come:

$d(p,q)=\underset{i}{\max }\{|p_i-q_i|\}$

dove $p_i$ e $q_i$ sono le coordinate standard di $p$ e $q$ rispettivamente. Equivale al limite della metrica nello spazio Lp:

$\underset{k\to \mathrm{\infty }}{\lim }(\sum _{i=1}^n{|p_i-q_i|}^k{)}^{1/k}$

ed è perciò anche nota come metrica $L_{\mathrm{\infty }}$. Si tratta della metrica indotta dalla norma del sup, ed è un esempio di metrica iniettiva.

In due dimensioni, per esempio nella geometria piana, se due punti $p$ e $q$ hanno coordinate cartesiane $(x_1,y_1)$ e $(x_2,y_2)$ la loro distanza è:

$d=\max (|x_2-x_1|,|y_2-y_1|)$

Con tale metrica una circonferenza di raggio $r$, cioè i punti a distanza $r$ dal centro, è un quadrato i cui lati hanno lunghezza $2r$ e sono paralleli agli assi coordinati.

Proprietà

In una dimensione tutte le metriche L_p sono uguali: sono il valore assoluto della differenza. In due dimensioni, la distanza di Chebyshev è equivalente ad una rotazione e una riscalatura della distanza di Manhattan planare. Una tale equivalenza tra le metriche L₁ e L_∞ non si generalizza tuttavia in dimensione maggiore. Una sfera costruita con la distanza di Chebyshev è infatti un cubo, mentre se costruita con la distanza di Manhattan è un'ottaedro.

Algoritmo di calcolo

La funzione in Python chebyshev_distance(), ad esempio, computa la distanza tra due vettori di uguale lunghezza:

def chebyshev_distance(v1, v2):
    #Return the Chebyshev distance between equal-length vectors
    if len(v1) != len(v2):
        raise ValueError("Undefined for vectors of unequal length")
    return max(abs(e1-e2) for e1, e2 in zip(v1, v2))

Bibliografia

• Template:Cita libro
• Template:Cita libro
• Template:Cita libro
• Template:Cita libro

Voci correlate

• Distanza (matematica)
• Geometria del taxi
• Norma uniforme
• Spazio Lp

Collegamenti esterni

• Template:Collegamenti esterni