Chebyshevafstand

Chebyshevafstand, ook wel L∞-afstand genoemd, is een metriek op de n-dimensionale Euclidische ruimte R^n. Voor twee punten x = (x1, ..., xn) en y = (y1, ..., yn) wordt de afstand gedefinieerd als d∞(x,y) = max_i |xi - yi|. Een equivalente formulering is d∞(x,y) = ||x - y||∞, waarbij ||·||∞ de L∞-norm is.

Geometrisch gezien correspondeert de eenheidsbol voor de L∞-afstand met een hypercube: de set van punten z met d∞(z,0) ≤ 1 vormt een kubus met zijden langs de assen. In het ruimere R^n heeft de unit-ruimte onder deze metric dus de vorm van een n-dimensionale kubus.

Eigenschappen en metriek: Chebyshevafstand voldoet aan de basiskenmerken van een metriek: non-negativiteit, symmetrie en de identiteit van de onderscheiden, plus de driehoekongelijkheid. Concreet betekent dit dat d∞(x,y) ≥ 0, d∞(x,y) = 0 precies wanneer x = y, d∞(x,y) = d∞(y,x), en d∞(x,z) ≤ d∞(x,y) + d∞(y,z) voor alle x,y,z.

Relaties met andere normen: voor elk vector v geldt ||v||∞ ≤ ||v||2 ≤ √n ||v||∞, en ||v||1 ≥ ||v||∞. Dit laat zien hoe de Chebyshevafstand zich verhoudt tot andere gangbare normen.

Schaakbordinterpretatie: in twee dimensies geeft d∞(x,y) het minimum aantal koning-stapjes aan om van x naar y te komen, omdat een koning in één stap tegelijk zowel horizontaal, verticaal als diagonaal kan bewegen.

Toepassingen: veelgebruikte toepassingen bevinden zich in pathfinding op rastergrids, bounding-boxberekeningen, distance transforms in beeldverwerking, clustering en nearest-neighbor zoekopdrachten onder L∞. Voorbeelden zijn gemakkelijk te berekenen en geschikt voor discrete ruimten.