Grafo de visibilidad

Dado un conjunto de obstáculos con forma poligonal en el plano euclidiano se dice que el grafo de visibilidad es aquel grafo en el cual cada nodo representa un vértice de los polígonos y las aristas son las conexiones visibles entre tales vértices.

Esto quiere decir que para cada arista en el grafo de visibilidad definida por

, el segmento de recta que conecta los vértices correspondientes en el plano no se interseca con ningún polígono (obstáculo).

[1]​ El algoritmo CalcularGrafoVisibilidad consiste en recorrer los vértices de todos los polígonos y a partir de cada uno determinar que vértices son visibles[2]​ .

El algoritmo para determinar que vértices son visibles recibe como entrada un punto y un conjunto de polígonos disjuntos los cuales son tratados como segmentos de recta, cabe señalar que los polígonos deben ser simples ya que en caso contrario los segmentos de recta se interesectarían entre sí dificultando mantener su estado.

pertenece a un polígono el cual obstaculiza también la línea de visión del vértice, el algoritmo presentado a continuación únicamente toma en cuenta la segunda consideración.

El algoritmo que calcula el grafo de visibilidad procesa los

vértices de los polígonos almacenando y removiendo cada arista como máximo una vez del árbol, las operaciones insertar, eliminar y obtener el elemento más a la izquierda toman

La verificación de vértice visible puede ser realizada en tiempo constante.

Cuando los obstáculos son barras de diferentes alturas ordenados en una línea, pueden ser entendidos como una serie temporal.