Matchande avstånd

I matematik är matchningsavståndet ett mått på utrymmet för storleksfunktioner .

Exempel: Matchningsavståndet mellan

\ell _{1}=r+a+b

och

\ell _{2}=r '+a'

ges av

d_{ \text{match}}(\ell _{1},\ell _{2})=\max\{\delta (r,r'),\delta (b,a'),\delta (a,\ Delta )\}=4

Kärnan i definitionen av matchande avstånd är observationen att informationen i en storleksfunktion kan lagras kombinatoriskt i en formell serie av linjer och punkter i planet, som kallas respektive hörnlinjer och hörnpunkter .

Med tanke på två storleksfunktioner $\ell _{1}$ och $\ell _{2}$ , låt $C_{1}$ (resp. $C_) {2}$ ) vara multiuppsättningen av alla hörnpunkter och hörnlinjer för $\ell _{1}$ (resp. $\ell _{2}$ ) räknade med deras multipliciteter, utökade genom att lägga till en räknebar oändlighet av punkter i diagonalen $\{(x,y)\in \mathbb {R} ^{2}:x=y\}$ .

Matchningsavståndet mellan $\ell _{1}$ och $\ell _{2}$ $d_{\text{match}}(\ell _{1},\ell _{2})=\min _{\sigma }\max _{p\in C_ {1}}\delta (p,\sigma (p))$ av ) där $\sigma$ varierar mellan alla bijektioner mellan $C_{1}$ och $C_{2}$ och

\delta \left((x,y),(x',y')\right)=\min \left\{\max\{|xx'|,|yy'|\},\max \ vänster\{{\frac {yx}{2}},{\frac {y'-x'}{2}}\right\}\right\}.

Grovt sett är matchningsavståndet $d_{\text{match}}$ mellan två storleksfunktioner det minsta, över alla matchningar mellan hörnpunkterna för de två storleksfunktionerna, av maximum av L $\ displaystyle L_{\infty }}$ -avstånd mellan två matchade hörnpunkter. Eftersom två storleksfunktioner kan ha olika antal hörnpunkter, kan dessa även matchas till punkter i diagonalen $\Delta$ . Dessutom innebär definitionen av $\delta$ att matchning av två punkter i diagonalen inte kostar något.

Se även