Un espace métrique (X, d) admet un plongement isométrique dans un espace (Y, d′) s’il existe une application Φ de X → Y telle que pour tout u, v ∈ X, d(u, v) = d′(Φ(u), Φ(v)). Décider si un espace métrique est plongeable dans un autre espace métrique isométriquement ou avec un faible facteur de distorsion est une question classique en géométrie des distances et trouve certaines applications en informatique théorique, visualisation et analyse de donnée.
Nous nous intéressons ici au plongement isométrique d’un espace métrique dans le plan avec norme l1 (ou la norme l∞ puisque dans le plan ces deux normes sont équivalentes). Bandelt et Chepoi (1996) ont montrés que le plongement isométrique dans le plan rectilinèaire peut être effectué si et seulement si tous les sous espace d’au plus 6 points peuvent l’être. Ce résultat implique que l’on peut décider ce problème en temps polynomial. Jeff Edmonds (2008) a donné un algorithme en O(n2log2 n) puis David Eppstein (2009) a donné un algorithme optimal en O(n2). Nous présentons un autre algorithme lui aussi en temps optimal O(n2) mais avec une approche différente.
Cet algorithme utilise l’injectivité du plan avec la norme l1 et le concept d’enveloppe injective introduite par Isbell (1964) et Dress (1984) pour plonger une quadruplet de points qui va assurer une certaine rigidité permettant par le suite d’étendre le plongement à l’ensemble de l’espace métrique. Si l’espace métrique de départ est plongeable isométriquement l’algorithme renvoie un des plongements possibles, sinon il renvoie une réponse négative.
Travail réalisé en collaboration avec Victor Chepoi et Yann Vaxès.
This document was translated from LATEX by HEVEA.