Gráfico de visibilidad

En geometría computacional y planificación de movimiento de robots , ^{[ 1 ]} un grafo de visibilidad es un grafo de ubicaciones intervisibles, típicamente para un conjunto de puntos y obstáculos en el plano euclidiano . Cada nodo en el grafo representa una ubicación puntual, y cada arista representa una conexión visible entre ellas. Es decir, si el segmento de línea que conecta dos ubicaciones no pasa por ningún obstáculo, se dibuja una arista entre ellas en el grafo. Cuando el conjunto de ubicaciones se encuentra en una línea, esto puede entenderse como una serie ordenada. Por lo tanto, los grafos de visibilidad se han extendido al ámbito del análisis de series temporales .

Los grafos de visibilidad pueden utilizarse para encontrar las rutas euclidianas más cortas entre un conjunto de obstáculos poligonales en el plano: la ruta más corta entre dos obstáculos sigue segmentos de línea recta excepto en los vértices de los obstáculos, donde puede girar, por lo que la ruta euclidiana más corta es la ruta más corta en un grafo de visibilidad que tiene como nodos los puntos de inicio y destino y los vértices de los obstáculos. ^{[ 2 ]} Por lo tanto, el problema de la ruta euclidiana más corta puede descomponerse en dos subproblemas más simples: la construcción del grafo de visibilidad y la aplicación de un algoritmo de ruta más corta, como el algoritmo de Dijkstra, al grafo. Para planificar el movimiento de un robot que tiene un tamaño no despreciable en comparación con los obstáculos, se puede utilizar un enfoque similar después de expandir los obstáculos para compensar el tamaño del robot. ^{[ 2 ]} Lozano-Pérez y Wesley (1979) atribuyen el método del gráfico de visibilidad para los caminos euclidianos más cortos a la investigación realizada en 1969 por Nils Nilsson sobre la planificación de movimiento para el robot Shakey , y también citan una descripción de este método de 1973 realizada por los matemáticos rusos MB Ignat'yev, FM Kulakov y AM Pokrovskiy.

Los gráficos de visibilidad también pueden utilizarse para calcular la ubicación de antenas de radio , o como herramienta empleada en arquitectura y planificación urbana mediante el análisis de gráficos de visibilidad .

El grafo de visibilidad de un conjunto de ubicaciones que se encuentran en una línea puede interpretarse como una representación teórica de grafos de una serie temporal. ^{[ 3 ]} Este caso particular establece un vínculo entre las series temporales , los sistemas dinámicos y la teoría de grafos .

El grafo de visibilidad de un polígono simple tiene sus vértices como ubicaciones de puntos y el exterior del polígono como único obstáculo. Los grafos de visibilidad de polígonos simples deben ser grafos hamiltonianos : el contorno del polígono forma un ciclo hamiltoniano en el grafo de visibilidad. Se sabe que no todos los grafos de visibilidad inducen un polígono simple. Sin embargo, aún se desconoce una caracterización algorítmica eficiente de los grafos de visibilidad de polígonos simples. Estos grafos no pertenecen a muchas familias conocidas de grafos bien estructurados: podrían no ser grafos perfectos , grafos circulares o grafos cordales . ^{[ 4 ]} Una excepción a este fenómeno es que los grafos de visibilidad de polígonos simples son grafos cop-win . ^{[ 5 ]}

Reconocer el grafo de visibilidad de un conjunto finito de puntos en el plano euclidiano es completo para la teoría existencial de los números reales . ^{[ 6 ]}

El problema de la galería de arte consiste en encontrar un pequeño conjunto de puntos tal que todos los demás puntos que no representen obstáculos sean visibles desde dicho conjunto. Ciertas variantes del problema de la galería de arte pueden interpretarse como la búsqueda de un conjunto dominante en un grafo de visibilidad.

Las bitangentes de un sistema de polígonos o curvas son líneas que tocan dos de ellos sin penetrarlos en sus puntos de contacto. Las bitangentes de un conjunto de polígonos forman un subconjunto del grafo de visibilidad, cuyos nodos son los vértices del polígono y los propios polígonos son los obstáculos. El método del grafo de visibilidad para el problema del camino euclidiano más corto puede acelerarse formando un grafo a partir de las bitangentes en lugar de utilizar todas las aristas de visibilidad, ya que un camino euclidiano más corto solo puede entrar o salir del límite de un obstáculo a lo largo de una bitangente. ^{[ 7 ]}

• Análisis de gráficos de visibilidad
• Análisis espacial arquitectónico difuso
• sintaxis de espacios

• de Berg, Mark; van Kreveld, Marc; Overmars, Marcos ; Schwarzkopf, Otfried (2000), "Capítulo 15: Gráficos de visibilidad", Geometría computacional (2ª  ed.), Springer-Verlag , págs. 307–317 , ISBN  978-3-540-65620-3.
• Lozano-Pérez, Tomás; Wesley, Michael A. (1979), "Un algoritmo para planificar trayectorias libres de colisiones entre obstáculos poliédricos", Communications of the ACM , 22 (10): 560– 570, doi : 10.1145/359156.359164 , S2CID 17397594 .

• VisiLibity: Una biblioteca C++ gratuita de código abierto con algoritmos de visibilidad de punto flotante y tipos de datos compatibles. Este software permite calcular gráficos de visibilidad de entornos poligonales con agujeros poligonales. También incluye una interfaz para Matlab.