Chebyshev avstånd

	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

Det diskreta Chebyshev-avståndet mellan två fält på ett schackbräde ger det minsta antal drag en kung behöver för att flytta mellan dem. Detta beror på att en kung kan röra sig diagonalt, så att hoppen för att täcka det mindre avståndet parallellt med en rang eller kolumn effektivt absorberas i hoppen som täcker den större. Ovan är Chebyshev-avstånden för varje kvadrat från kvadraten f6.

I matematik är Chebyshev-avstånd (eller Tchebychev-avstånd ), maximum metric , eller L _∞ -metrisk ett mått som definieras på ett vektorrum där avståndet mellan två vektorer är den största av deras skillnader längs någon koordinatdimension. Den är uppkallad efter Pafnuty Chebyshev .

Det är också känt som schackbrädesavstånd , eftersom i schackspel är det minsta antal drag som en kung behöver för att gå från en ruta på ett schackbräde till en annan lika med Chebyshev-avståndet mellan rutornas mittpunkter, om rutorna har sidolängd en, som representerad i 2-D rumsliga koordinater med axlar i linje med brädans kanter. Till exempel är Chebyshev-avståndet mellan f6 och e2 lika med 4.

Definition

Chebyshev-avståndet mellan två vektorer eller punkter x och y , med standardkoordinater $x_{i}$ respektive $y_{i}$ , är

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

Detta är lika med gränsen för L _p -måtten :

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

därför är den också känd som L _∞ -metriken.

Matematiskt är Chebyshev-avståndet ett mått som induceras av den högsta normen eller enhetliga normen . Det är ett exempel på ett injektivt mått .

I två dimensioner, dvs plan geometri , om punkterna p och q har kartesiska koordinater $(x_{1},y_{1})$ och $(x_{2},y_{2})$ , deras Chebyshev-avstånd är

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

Under denna metrik är en cirkel med radie r , som är uppsättningen av punkter med Chebyshev avstånd r från en mittpunkt, en kvadrat vars sidor har längden 2 r och är parallella med koordinataxlarna.

På ett schackbräde, där man använder ett diskret Chebyshev-avstånd, snarare än ett kontinuerligt, är cirkeln med radien r en kvadrat med sidolängderna 2 r, mätt från kvadraternas centrum, och därför innehåller varje sida 2 r +1 rutor ; till exempel är cirkeln med radie 1 på ett schackbräde en kvadrat på 3×3.

Egenskaper

I en dimension är alla L _p -mått lika – de är bara det absoluta värdet av skillnaden.

Det tvådimensionella Manhattan-avståndet har "cirklar", dvs nivåuppsättningar i form av kvadrater, med sidor av längden √ 2 r , orienterade i en vinkel på π/4 (45°) mot koordinataxlarna, så det plana Chebyshev-avståndet kan vara ses som ekvivalent genom rotation och skalning till (dvs en linjär transformation av) det plana Manhattan-avståndet.

Denna geometriska ekvivalens mellan L ₁ och L _∞ -måtten generaliserar dock inte till högre dimensioner. En sfär bildad med hjälp av Chebyshev-avståndet som metrik är en kub med varje yta vinkelrät mot en av koordinataxlarna, men en sfär som bildas med Manhattan-avståndet är en oktaeder : dessa är dubbla polyedrar , men bland kuber, bara kvadraten (och 1) -dimensionellt linjesegment) är självdubbla polytoper . Ändå är det sant att i alla änddimensionella rum är L _1- och L _∞ -måtten matematiskt dubbla till varandra.

På ett rutnät (som ett schackbräde) är punkterna på ett Chebyshev-avstånd på 1 av en punkt Moore-området för den punkten.

Chebyshev-avståndet är gränsfallet för order- $p$ Minkowski-avståndet , när $p$ når oändligheten .

Ansökningar

Chebyshev-avståndet används ibland i lagerlogistik , eftersom det effektivt mäter den tid det tar för en travers att flytta ett föremål (eftersom kranen kan röra sig på x- och y - axlarna samtidigt men med samma hastighet längs varje axel).

Det används också i stor utsträckning i elektroniska datorstödda tillverkningsapplikationer (CAM), i synnerhet i optimeringsalgoritmer för dessa. Många verktyg, såsom plottnings- eller borrmaskiner, fotoplotter , etc. som arbetar i planet, styrs vanligtvis av två motorer i x- och y-riktningar, liknande traverskranarna.

Se även