Gráfico Semi-Yao
El gráfico k -semi-Yao ( k -SYG ) de un conjunto de n objetos P es un gráfico de proximidad geométrica, que se describió por primera vez para presentar una estructura de datos cinéticos para el mantenimiento de todos los vecinos más cercanos en objetos en movimiento. [1] Recibe su nombre por su relación con el gráfico de Yao , que lleva el nombre de Andrew Yao .
El k -SYG se construye de la siguiente manera. El espacio alrededor de cada punto p en P se divide en un conjunto de conos poliédricos de ángulo de apertura , lo que significa que el ángulo de cada par de rayos dentro de un cono poliédrico que emana del vértice es como máximo , y luego p se conecta a k puntos de P en cada uno de los conos poliédricos cuya proyección sobre el eje del cono es mínima.
