En geometría computacional y planificación de movimiento de robots , [1] un gráfico de visibilidad es un gráfico de ubicaciones intervisibles, típicamente para un conjunto de puntos y obstáculos en el plano euclidiano . Cada nodo en el gráfico representa una ubicación de punto, y cada borde representa una conexión visible entre ellos. Es decir, si el segmento de línea que conecta dos ubicaciones no pasa por ningún obstáculo, se dibuja un borde entre ellos en el gráfico. Cuando el conjunto de ubicaciones se encuentra en una línea, esto puede entenderse como una serie ordenada. Por lo tanto, los gráficos de visibilidad se han extendido al ámbito del análisis de series de tiempo .
Los gráficos de visibilidad se pueden utilizar para encontrar caminos euclidianos más cortos entre un conjunto de obstáculos poligonales en el plano: el camino más corto 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 el camino más corto euclidiano es el camino más corto en un gráfico 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 del camino más corto euclidiano se puede descomponer en dos subproblemas más simples: construir el gráfico de visibilidad y aplicar un algoritmo de camino más corto como el algoritmo de Dijkstra al gráfico. 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 más cortos euclidianos a la investigación de 1969 de Nils Nilsson sobre la planificación del 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 se pueden utilizar para calcular la ubicación de antenas de radio , o como una herramienta utilizada en arquitectura y planificación urbana a través del análisis de gráficos de visibilidad .
El gráfico de visibilidad de un conjunto de ubicaciones que se encuentran en una línea se puede interpretar como una representación teórica de gráficos de una serie de tiempo. [3] Este caso particular construye un puente entre las series de tiempo , los sistemas dinámicos y la teoría de grafos .
El gráfico de visibilidad de un polígono simple tiene los vértices del polígono como sus ubicaciones de puntos y el exterior del polígono como el único obstáculo. Los gráficos de visibilidad de polígonos simples deben ser gráficos hamiltonianos : el límite del polígono forma un ciclo hamiltoniano en el gráfico de visibilidad. Se sabe que no todos los gráficos de visibilidad inducen un polígono simple. Sin embargo, sigue siendo desconocida una caracterización algorítmica eficiente de los gráficos de visibilidad de polígonos simples. Estos gráficos no entran en muchas familias conocidas de gráficos bien estructurados: podrían no ser gráficos perfectos , gráficos circulares o gráficos cordales . [4] Una excepción a este fenómeno es que los gráficos de visibilidad de polígonos simples son gráficos cop-win . [5]
El problema de la galería de arte consiste en encontrar un conjunto pequeño de puntos de manera que todos los demás puntos que no sean obstáculos sean visibles desde ese conjunto. Algunas formas del problema de la galería de arte pueden interpretarse como la búsqueda de un conjunto dominante en un gráfico de visibilidad.
Las bitangentes de un sistema de polígonos o curvas son líneas que tocan a 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 que tiene los vértices del polígono como sus nodos y los polígonos mismos como obstáculos. El enfoque del grafo de visibilidad para el problema del camino más corto euclidiano puede acelerarse formando un grafo a partir de las bitangentes en lugar de utilizar todos los bordes de visibilidad, ya que un camino más corto euclidiano solo puede entrar o salir del límite de un obstáculo a lo largo de una bitangente. [6]