En geometría computacional y planificación de movimiento robots , un gráfico de visibilidad es un gráfico de visibilidad mutua de puntos en el espacio, generalmente para un conjunto de puntos y obstáculos en el plano euclidiano . Cualquier vértice en el gráfico representa un punto en el espacio y cualquier borde representa la línea de visión entre los puntos. Es decir, si un segmento de línea recta que conecta dos puntos en el espacio no pasa por ningún obstáculo, se dibujará un borde en el gráfico. Si el conjunto de puntos en el espacio se encuentra en una línea, se pueden entender como una secuencia ordenada. Los gráficos de visibilidad se extienden así al ámbito de análisisserie de tiempo
Los gráficos de visibilidad se pueden usar para encontrar los caminos más cortos entre obstáculos poligonales en un plano: el camino más corto entre dos obstáculos es en línea recta y gira en los vértices de los obstáculos, por lo que el camino más corto es el camino más corto en la visibilidad gráfico cuyos vértices son los puntos inicial y final y las cimas de los obstáculos [1] [2] . Por lo tanto, el problema de la ruta más corta se puede dividir en dos problemas más simples: construir un gráfico de visibilidad y aplicar un algoritmo de ruta más corta como el algoritmo de Dijkstra al gráfico . Para planificar el movimiento de un robot que tiene un tamaño notable en comparación con los obstáculos, se puede usar un enfoque similar aumentando los obstáculos para compensar el tamaño del robot [1] [2] . Lozano-Peretz y Wesley [2] atribuyen el método del gráfico de visibilidad para el camino más corto en el plano euclidiano a un estudio de 1969 de Nils Nilsson sobre la planificación del movimiento del robot Sheka y citan una descripción de este método en 1973 por los matemáticos rusos M. B. Ignatiev , F. M. Kulakov y A. M. Pokrovsky.
Los gráficos de visibilidad también se pueden utilizar para calcular la posición de antenas de radio o como una herramienta en arquitectura y urbanismo en el análisis de visibilidad .
Si el conjunto de puntos del espacio se encuentra en una línea recta, se pueden entender como una secuencia ordenada [3] . Este caso especial 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 (es decir, sin lados cruzados) tiene los vértices como puntos en el espacio y la región exterior del polígono como una obstrucción. Los gráficos de visibilidad de polígonos simples deben ser hamiltonianos : el límite de un polígono forma un ciclo hamiltoniano en el gráfico de visibilidad. Se sabe que no todos los gráficos de visibilidad forman un polígono simple. De hecho, los gráficos de visibilidad de polígonos simples no tienen las características de ninguna clase de gráficos [4] .
El problema de la galería de imágenes es el problema de encontrar un pequeño conjunto de puntos tal que todos los demás puntos sean visibles desde los puntos de este conjunto. Algunas formas del problema de la galería de arte pueden interpretarse como encontrar un conjunto dominante en un gráfico de visibilidad.
Los sistemas bitangentes de polígonos o curvas son líneas que son tangentes a dos polígonos. Los conjuntos de polígonos bitangentes forman un subconjunto del gráfico de visibilidad que tiene vértices de polígono como vértices de gráfico (puntos en el espacio), los polígonos sirven como obstáculos. El gráfico de visibilidad para el problema de encontrar la ruta más corta se puede mejorar formando bitangentes en lugar de todos los bordes de visibilidad, ya que la ruta más corta solo puede pasar a lo largo de bitangentes [5] .