El k-semigrafo de Yao (k-SYG por sus siglas en inglés) de un conjunto P de n objetos, es un tipo de grafo 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. Está relacionado con el grafo de Yao, que lleva el nombre de Andrew Chi-Chih Yao.
Construcción El k semigrafo de Yao 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 cuyas proyecciones sobre el eje del cono son mínimas.
Propiedades El k semigrafo de Yao cuando k = 1 se conoce como grafo theta y es la unión de dos triangulaciones de Delaunay. Para un pequeño y un eje de cono apropiado, el ksemigrafo de Yao proporciona un supergrafo del k-grafo del vecino más cercano (k-NNG). Por ejemplo, en 2D, si se divide el plano alrededor de cada punto en seis cuñas de ángulos iguales y se seleccionan los ejes del cono en las direcciones de las bisectrices del cono, se obtiene un k-semigrafo de Yao como supergrafo para k-grafo del vecino más cercano.
Véase también Extensor geométrico
Referencias
Categoría:Geometría computacional Categoría:Grafos geométricos