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 k-SYG is constructed as follows. 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.