The k-semi-Yao graph (k-SYG) of a set of n objects P is a geometric proximity graph, which was first described to present a kinetic data structure for maintenance of all the nearest neighbors on moving objects.
[1] It is named for its relation to the Yao graph, which is named after Andrew Yao.
The space around each point p in P is partitioned into a set of polyhedral cones of opening angle
, meaning the angle of each pair of rays inside a polyhedral cone emanating from the apex is at most
, and then p connects to k points of P in each of the polyhedral cones whose projections on the cone axis is minimum.