Distance de chanfrein

Une pondération est un couple ${\displaystyle (\mathbf {x} ,w)}$ où ${\displaystyle \mathbf {x} }$ est un point (le déplacement) et ${\displaystyle w}$ un entier. Un masque ${\displaystyle {\mathcal {M}}}$ est un ensemble fini de pondérations : ${\displaystyle {\mathcal {M}}=\left\{(\mathbf {x} _{i},w_{i})\right\}}$. Un masque de chanfrein est un masque possédant une symétrie centrale, dont les poids sont strictement positifs et les déplacements non nuls.

Il est possible de trouver un chemin entre deux points ${\displaystyle p}$ et ${\displaystyle q}$ en utilisant les déplacements d'un masque de chanfrein. Soit ${\displaystyle {\mathcal {M}}=\left\{(\mathbf {x} _{i},w_{i})\right\}}$ un masque de chanfrein, alors

${\displaystyle q=p+\sum \lambda _{i}\mathbf {x} _{i}}$,

où ${\displaystyle \lambda _{i}}$ est un entier qui correspond au nombre de fois que le déplacement ${\displaystyle \mathbf {x} _{i}}$ est effectué.

Une distance de chanfrein ${\displaystyle d_{\mathcal {M}}}$ entre deux points ${\displaystyle p}$ et ${\displaystyle q}$ d'un espace discret est le coût minimal ${\displaystyle \sum \lambda _{i}w_{i}}$ de tous les chemins de longueur finie ${\displaystyle \sum \lambda _{i}\mathbf {x} _{i}}$ entre ${\displaystyle p}$ et ${\displaystyle q}$ et utilisant les déplacements ${\displaystyle \mathbf {x} _{i}}$ du masque ${\displaystyle {\mathcal {M}}}$ :

${\displaystyle d_{\mathcal {M}}=\min \left\{\sum \lambda _{i}w_{i}\left|q=p+\sum \lambda _{i}\mathbf {x} _{i}\right.\right\}}$.

• Portail de la géométrie