Distanță Cebîșev

În matematică, distanța Cebîșev, metrică maximă sau metrică L_∞ este o metrică definită într-un spațiu vectorial unde distanța dintre doi vectori este valoarea cea mai mare dintre diferențele dintre ei de-a lungul oricărei coordonate. Este numită astfel după Pafnuti Cebîșev.

	a	b	c	d	e	f	g	h
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	a	b	c	d	e	f	g	h

Distanța Cebîșev dintre două câmpuri (pătrate) de pe o tablă de șah dă numărul minim de mișcări de care are nevoie un rege pentru a se deplasa de la unul la celălalt. Acest lucru se datorează faptului că un rege se poate mișca în diagonală, astfel încât unele mișcări paralele cu rândurile sau coloanele, pe o distanță mai mică, să fie comasate efectiv în mișcările pe diagonală, mai lungi. În imagine sunt distanțele Cebîșev ale fiecărui câmp față de câmpul f6.

Este cunoscută și ca distanța pe tabla de șah, deoarece în jocul de șah numărul minim de mutări necesare unui rege pentru a se deplasa de pe un câmp (pătrat) al tablei de șah pe altul este echivalent cu distanța Cebîșev dintre centrele acestor câmpuri, considerate ca având latura egală cu unitatea, iar coordonatele sunt pentru două dimensiuni și sunt aliniate cu laturile tablei. De exemplu, distanța Cebîșev dintre câmpurile f6 și e2 este 4 (v. figura de alături).

Definiție

Distanța Cebîșev între două puncte x and y, cu coordonatele standard $x_{i}$ și respectiv $y_{i}$ este

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

Aceasta este egală cu limita metricii spațiului L_p:

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

prin urmare este cunoscută și ca metrica L_∞.

Matematic, distanța Cebîșev este o metrică generată de norma uniformă (norma supremum). Este un exemplu de metrică injectivă.

În două dimensiuni, adică în geometria plană, dacă punctele p și q au coordonatele carteziene $(x_{1},y_{1})$ și $(x_{2},y_{2})$, distanța lor Cebîșev este

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

În această metrică, un cerc cu raza r, care este mulțimea punctelor cu distanța Cebîșev r față de centru, este pătratul ale cărui laturi au lungimea 2r și sunt paralele cu axele de coordonate.

Pe o tablă de șah, unde se folosește o distanță Cebîșev „discretă” în loc de una continuă, cercul de rază "r" este un pătrat cu lungimea laturilor 2r, măsurată între centrele câmpurilor de pe tablă, astfel fiecare parte conține 2r + 1 câmpuri; de exemplu, cercul de rază 1 pe o tablă de șah este un pătrat de 3×3 câmpuri.

Proprietăți

Într-o singură dimensiune, toate metricile L_p sunt egale — ele sunt valorile absolute ale diferențelor.

Distanța Manhattan bidimensională are „cercuri” adică linii de nivel sub formă de pătrate, cu laturile de lungime √2r, orientate la unghiul de $\pi /4$ (45°) față de axele de coordonate, astfel încât distanța Cebîșev din plan poate fi privită ca echivalentă prin rotație și scalare (adică printr-o transformare liniară) cu distanța Manhattan din plan.

Totuși, această echivalență geometrică între valorile L₁ și L_∞ nu se generalizează pentru dimensiuni superioare. O sferă formată folosind ca metrică distanța Cebîșev este un cub cu fiecare față perpendiculară pe una dintre axele de coordonate, dar o sferă formată folosind distanța Manhattan este un octaedru: acestea sunt poliedre duale, dar dintre cuburi, numai pătratul (și segmentul de dreaptă, unidimensional) sunt politopuri autoduale. Însă este adevărat că în toate spațiile cu dimensiuni finite metricile L₁ și L_∞ sunt matematic duale între ele.

Pe o grilă (cum ar fi o tablă de șah), punctele aflate la o distanță Cebîșev de 1 de un punct sunt vecinătatea Moore al acelui punct.

Distanța Cebîșev este cazul limită al distanței Minkowski de ordinul p când p tinde la infinit.

Aplicații

Distanța Cebîșev este uneori folosită în logistica depozitelor, întrucât măsoară efectiv timpul necesar unei macarale pentru a muta un obiect (deoarece macaraua se poate deplasa pe axele x și y în același timp, dar cu aceeași viteză de-a lungul fiecărei axe).

Este, de asemenea, utilizat pe scară largă în aplicațiile privind fabricația asistată de calculator (în engleză Computer-aided manufacturing – CAM), în special în algoritmii de optimizare a acestora. Multe mașini-unelte, cum ar fi mașinile de trasat sau găurit, plottere etc., care funcționează în plan, sunt de obicei acționate de două motoare în direcțiile x și y, asemănător cu podurile rulante.