Distanță Cebîșev
În matematică, distanța Cebîșev, metrică maximă sau metrică L∞[1] 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.[2] Este numită astfel după Pafnuti Cebîșev.
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.[3] De exemplu, distanța Cebîșev dintre câmpurile f6 și e2 este 4 (v. figura de alături).
Definiție
[modificare | modificare sursă]Distanța Cebîșev între două puncte x and y, cu coordonatele standard și respectiv este
Aceasta este egală cu limita metricii spațiului Lp:
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 și , distanța lor Cebîșev este
Î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
[modificare | modificare sursă]Într-o singură dimensiune, toate metricile Lp 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 (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 L1 ș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 L1 ș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
[modificare | modificare sursă]Distanța Cebîșev este uneori folosită în logistica depozitelor,[4] î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.[5]
Note
[modificare | modificare sursă]- ^ en Cyrus. D. Cantrell (). Modern Mathematical Methods for Physicists and Engineers. Cambridge University Press. ISBN 0-521-59827-3.
- ^ en James M. Abello, Panos M. Pardalos, and Mauricio G. C. Resende (editors) (). Handbook of Massive Data Sets. Springer. ISBN 1-4020-0489-3.
- ^ en David M. J. Tax; Robert Duin; Dick De Ridder (). Classification, Parameter Estimation and State Estimation: An Engineering Approach Using MATLAB. John Wiley and Sons. ISBN 0-470-09013-8.
- ^ en André Langevin; Diane Riopel (). Logistics Systems. Springer. ISBN 0-387-24971-0.
- ^ en Seitz, Charles L. (). Advanced Research in VLSI: Proceedings of the Decennial Caltech Conference on VLSI, March 1989. ISBN 9780262192828.