Distancia de Chebyshev

Métrica matemática

La distancia discreta de Chebyshev entre dos casillas de un tablero de ajedrez indica el número mínimo de movimientos que necesita un rey para moverse entre ellas. Esto se debe a que el rey puede moverse en diagonal, de modo que los saltos para cubrir la distancia más pequeña en paralelo a una fila o columna se absorben de manera efectiva en los saltos para cubrir la distancia más grande. Arriba se muestran las distancias de Chebyshev de cada casilla desde la casilla f6.

En matemáticas , la distancia de Chebyshev (o distancia de Tchebychev ), métrica máxima o métrica L _∞ ^[1] es una métrica definida en un espacio de coordenadas reales donde la distancia entre dos puntos es la mayor de sus diferencias a lo largo de cualquier dimensión de coordenadas. ^[2] Lleva el nombre de Pafnuty Chebyshev .

También se conoce como distancia del tablero de ajedrez , ya que en el juego de ajedrez el número mínimo de movimientos que necesita un rey para pasar de una casilla a otra en un tablero de ajedrez es igual a la distancia de Chebyshev entre los centros de las casillas, si las casillas tienen longitud de lado uno, como se representa en coordenadas espaciales 2-D con ejes alineados a los bordes del tablero. ^[3] Por ejemplo, la distancia de Chebyshev entre f6 y e2 es igual a 4.

Definición

La distancia de Chebyshev entre dos vectores o puntos x e y , con coordenadas estándar y , respectivamente, es ${\displaystyle x_{i}}$ ${\displaystyle y_{i}}$

${\displaystyle D_{\rm {Chebyshev}}(x,y):=\max _{i}(|x_{i}-y_{i}|).\ }$

Esto es igual al límite de la métrica L p :

${\displaystyle \lim _{p\to \infty }{\bigg (}\sum _{i=1}^{n}\left|x_{i}-y_{i}\right|^{p}{\bigg )}^{1/p},}$

Por lo tanto, también se conoce como métrica L _∞ .

Matemáticamente, la distancia de Chebyshev es una métrica inducida por la norma suprema o norma uniforme . Es un ejemplo de métrica inyectiva .

En dos dimensiones, es decir, geometría plana , si los puntos p y q tienen coordenadas cartesianas y , su distancia de Chebyshev es ${\displaystyle (x_{1},y_{1})}$ ${\displaystyle (x_{2},y_{2})}$

${\displaystyle D_{\rm {Chebyshev}}=\max \left(\left|x_{2}-x_{1}\right|,\left|y_{2}-y_{1}\right|\right).}$

Según esta métrica, un círculo de radio r , que es el conjunto de puntos con distancia de Chebyshev r desde un punto central, es un cuadrado cuyos lados tienen una longitud de 2 r y son paralelos a los ejes de coordenadas.

En un tablero de ajedrez, donde se utiliza una distancia de Chebyshev discreta , en lugar de una continua, el círculo de radio r es un cuadrado de lados de longitud 2 r, medidos desde los centros de los cuadrados, y por lo tanto cada lado contiene 2 r +1 cuadrados; por ejemplo, el círculo de radio 1 en un tablero de ajedrez es un cuadrado de 3×3.

Propiedades

Comparación de las distancias de Chebyshev, Euclidiana y Manhattan para la hipotenusa de un triángulo 3-4-5 en un tablero de ajedrez

En una dimensión, todas las métricas L _p son iguales: son solo el valor absoluto de la diferencia.

La distancia de Manhattan bidimensional tiene "círculos", es decir, conjuntos de niveles en forma de cuadrados, con lados de longitud √ 2 r , orientados en un ángulo de π/4 (45°) con respecto a los ejes de coordenadas, por lo que la distancia de Chebyshev plana puede verse como equivalente por rotación y escala a (es decir, una transformación lineal de) la distancia de Manhattan plana.

Sin embargo, esta equivalencia geométrica entre las métricas L ₁ y L _∞ no se generaliza a dimensiones superiores. Una esfera formada utilizando la distancia de Chebyshev como métrica es un cubo con cada cara perpendicular a uno de los ejes de coordenadas, pero una esfera formada utilizando la distancia de Manhattan es un octaedro : estos son poliedros duales , pero entre los cubos, solo el cuadrado (y el segmento de línea unidimensional) son politopos autoduales . Sin embargo, es cierto que en todos los espacios de dimensión finita las métricas L ₁ y L _∞ son matemáticamente duales entre sí.

En una cuadrícula (como un tablero de ajedrez), los puntos a una distancia de Chebyshev de 1 de un punto son el vecindario de Moore de ese punto.

La distancia de Chebyshev es el caso límite de la distancia de orden Minkowski , cuando llega al infinito . ${\displaystyle p}$ ${\displaystyle p}$

Aplicaciones

La distancia de Chebyshev se utiliza a veces en la logística de almacenes , ^[4] ya que mide eficazmente el tiempo que tarda una grúa aérea en mover un objeto (ya que la grúa puede moverse en los ejes x e y al mismo tiempo, pero a la misma velocidad a lo largo de cada eje).

También se utiliza ampliamente en aplicaciones de fabricación asistida por computadora (CAM) electrónica , en particular, en algoritmos de optimización para estas. Muchas herramientas, como máquinas de trazado o taladrado, fotoplotter , etc. que operan en el plano, generalmente están controladas por dos motores en direcciones x e y, de manera similar a las grúas aéreas. ^[5]

Generalizaciones

Para el espacio de secuencias de longitud infinita de números reales o complejos, la distancia de Chebyshev se generaliza a la norma ; esta norma a veces se denomina norma de Chebyshev. Para el espacio de funciones (reales o de valores complejos), la distancia de Chebyshev se generaliza a la norma uniforme . ${\displaystyle \ell ^{\infty }}$

Véase también

• Gráfica del rey
• Geometría del taxi

Referencias

1. Cyrus D. Cantrell (2000). Métodos matemáticos modernos para físicos e ingenieros . Cambridge University Press. ISBN 0-521-59827-3.
2. Abello, James M.; Pardalos, Panos M.; Resende, Mauricio GC , eds. (2002). Manual de conjuntos de datos masivos . Springer. ISBN 1-4020-0489-3.
3. David MJ Tax; Robert Duin; Dick De Ridder (2004). Clasificación, estimación de parámetros y estimación de estado: un enfoque de ingeniería con MATLAB . John Wiley and Sons. ISBN 0-470-09013-8.
4. André Langevin; Diane Riopel (2005). Sistemas logísticos. Springer. ISBN 0-387-24971-0.
5. Seitz, Charles L. (1989). Investigación avanzada en VLSI: Actas de la Conferencia decenal de Caltech sobre VLSI, marzo de 1989. ISBN 9780262192828.