Chebyshevavstand

Chebyshevavstand, kjent som Chebyshev-distansen eller L∞-normen, er en av målene som brukes i geometri og analyse for å måle avstand mellom to punkter i et n-dimensjonalt rom. For to punkter x og y i Real^n er Chebyshevavstanden definert som d∞(x,y) = max_i |x_i − y_i|. I to dimensjoner reduseres dette til d∞((x1,y1),(x2,y2)) = max(|x1−x2|, |y1−y2|).

Geometrisk sett har Chebyshevavstanden klare egenskaper: enhetens kule under denne metrikken er en firkant (i 2D) eller en hyperkube i høyere dimensjoner, axis-aligned i alle fall. I praksis betyr dette at nivåsettene av konstant avstand er kvadratiske former med sider parallell med koordinataksetene. En kjent tolkning er i sjakk: avstanden mellom to ruter tilsvarer det minste antallet trekk en konge trenger for å bevege seg fra en rute til en annen når kongeens hvert trekk koster 1.

Chebyshevavstanden er en metrics: den oppfyller ikke-negativitet, identitet av indiscernibles, symmetri og trekantslikningen. Den er også relasjonen til L∞-normen, siden d∞(x,y) = ||x − y||∞. I praksis er beregningen enkel og rask å utføre, noe som gjør den populær i algoritmer som kartlegger gridbaserte rom og i grunnleggende maskinlæring og bildebehandling.

Vanlige anvendelser inkluderer rasjonelle heuristikker i A*-algoritmer for gridbasert ruteplanlegging (særlig i åpent 8-nabolag), og i analyser der like vektede steg i mange retninger antas å ha lik kostnad. Chebyshevavstand kan også generaliseres til flere dimensjoner for å måle avstand i datarom og i bildebehandling.