Gráfico de vecindad relativa

Un gráfico de vecindad relativa es un gráfico no dirigido definido en un conjunto de puntos en el plano euclidiano al conectar dos puntos p y q con un borde cuando no hay un tercer punto r que esté más cerca de p y q que p y q entre sí. otro. Este gráfico fue propuesto por Godfried Toussaint en 1980 como una forma de definir una estructura sobre un conjunto de puntos que refleja la percepción humana de la forma del conjunto [1] [2] [3] .

Algoritmos

Supovit [4] mostró cómo construir de manera eficiente un gráfico de vecindad relativa en tiempo O( n  log  n ) [5] . El gráfico se puede calcular en tiempo medio O ( n ) para un conjunto arbitrario de puntos uniformemente distribuidos en el cuadrado unitario [6] . El gráfico de vecindad relativa se puede calcular en tiempo lineal a partir de la triangulación de Delaunay de un conjunto de puntos [7] [8] .

Generalizaciones

Dado que un gráfico se define solo en términos de distancias entre puntos, un gráfico de vecindad relativa se puede definir para conjuntos de puntos en un espacio de cualquier dimensión [1] [9] y para métricas no euclidianas [1] [7] [10 ] [11] .

Gráficos relacionados

El gráfico de vecindad relativa es un ejemplo de un núcleo beta basado en . Este es un subgrafo de la triangulación de Delaunay . A su vez, el árbol de expansión mínimo euclidiano es su subgrafo, lo que implica que es un grafo conexo .

El gráfico de Urquhart , formado al eliminar el borde más largo de cada triángulo en una triangulación de Delaunay, se propuso originalmente como un método rápido para calcular un gráfico de vecindad relativa [12] . Aunque el gráfico de Urquhart a veces es diferente del gráfico de vecindad relativa [13] , se puede utilizar como una aproximación al gráfico de vecindad relativa [14] .

Notas

  1. ↑ 1 2 3 Jaromczyk, Kowaluk, 1991 , pág. 181–191.
  2. ↑ Toussaint, 1980 , pág. 261–268.
  3. ↑ Jaromczyk, Toussaint, 1992 , pág. 1502-1517
  4. ↑ Supowit, 1983 .
  5. ↑ Supowit, 1983 , pág. 428–448.
  6. ↑ Katajainen, Nevalainen, Teuhola, 1987 , p. 77–86.
  7. ↑ 1 2 Jaromczyk, Kowaluk, 1987 , p. 233–241.
  8. ↑ Lingas, 1994 , pág. 199–208.
  9. ↑ Agarwal, Matousek, 1992 , pág. 58–65.
  10. ↑ O'Rourke, 1982 , pág. 189–192.
  11. ↑ Lee, 1985 , pág. 327–332.
  12. ↑ Urquhart, 1980 , pág. 556–557.
  13. ↑ Toussaint, 1980 , pág. 860.
  14. ↑ Andrade, de Figueiredo, 2001 .

Literatura