Graphique de visibilité

En géométrie computationnelle et en planification de mouvements de robots , un graphe de visibilité est un graphe d'emplacements intervisibles, généralement pour un ensemble de points et d'obstacles dans le plan euclidien . Chaque nœud du graphe représente un emplacement de point et chaque arête représente une connexion visible entre eux. Autrement dit, si le segment de ligne reliant deux emplacements ne traverse aucun obstacle, une arête est tracée entre eux dans le graphe. Lorsque l'ensemble des emplacements se trouve sur une ligne, cela peut être compris comme une série ordonnée. Les graphes de visibilité ont donc été étendus au domaine de l' analyse des séries chronologiques .

Les graphes de visibilité peuvent être utilisés pour trouver les chemins les plus courts euclidiens parmi un ensemble d' obstacles polygonaux dans le plan : le chemin le plus court entre deux obstacles suit des segments de ligne droite sauf aux sommets des obstacles, où il peut tourner, de sorte que le chemin le plus court euclidien est le chemin le plus court dans un graphe de visibilité qui a comme nœuds les points de départ et de destination et les sommets des obstacles. Par conséquent, le problème du chemin le plus court euclidien peut être décomposé en deux sous-problèmes plus simples : construire le graphe de visibilité et appliquer un algorithme de chemin le plus court tel que l'algorithme de Dijkstra au graphe. Pour planifier le mouvement d'un robot qui a une taille non négligeable par rapport aux obstacles, une approche similaire peut être utilisée après avoir étendu les obstacles pour compenser la taille du robot. Lozano-Pérez et Wesley (1979) attribuent la méthode du graphe de visibilité pour les plus courts chemins euclidiens aux recherches menées en 1969 par Nils Nilsson sur la planification du mouvement du robot Shakey , et citent également une description de cette méthode en 1973 par les mathématiciens russes MB Ignat'yev, FM Kulakov et AM Pokrovskiy.

Les graphiques de visibilité peuvent également être utilisés pour calculer le placement des antennes radio , ou comme outil utilisé dans l'architecture et l'urbanisme grâce à l'analyse des graphiques de visibilité .

Le graphique de visibilité d'un ensemble d'emplacements situés sur une ligne peut être interprété comme une représentation théorique des graphes d'une série temporelle. Ce cas particulier établit un pont entre les séries temporelles , les systèmes dynamiques et la théorie des graphes .

Le graphe de visibilité d'un polygone simple a les sommets du polygone comme emplacements de points, et l'extérieur du polygone comme seul obstacle. Les graphes de visibilité des polygones simples doivent être des graphes hamiltoniens : la frontière du polygone forme un cycle hamiltonien dans le graphe de visibilité. Il est connu que tous les graphes de visibilité n'induisent pas un polygone simple. Cependant, une caractérisation algorithmique efficace des graphes de visibilité des polygones simples reste inconnue. Ces graphes n'appartiennent pas à de nombreuses familles connues de graphes bien structurés : ils peuvent ne pas être des graphes parfaits , des graphes circulaires ou des graphes chordaux . Une exception à ce phénomène est que les graphes de visibilité des polygones simples sont des graphes cop-win .

Le problème de la galerie d'art consiste à trouver un petit ensemble de points tels que tous les autres points non-obstacles soient visibles à partir de cet ensemble. Certaines formes du problème de la galerie d'art peuvent être interprétées comme la recherche d'un ensemble dominant dans un graphe de visibilité.

Les bitangentes d'un système de polygones ou de courbes sont des lignes qui touchent deux d'entre eux sans les pénétrer à leurs points de contact. Les bitangentes d'un ensemble de polygones forment un sous-ensemble du graphe de visibilité qui a les sommets du polygone comme nœuds et les polygones eux-mêmes comme obstacles. L'approche du graphe de visibilité pour le problème du plus court chemin euclidien peut être accélérée en formant un graphe à partir des bitangentes au lieu d'utiliser toutes les arêtes de visibilité, puisqu'un plus court chemin euclidien ne peut entrer ou sortir de la frontière d'un obstacle que le long d'une bitangente.