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.
It is named for its relation to the
Yao graph, which is named after
Andrew Yao.
Construction
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.
Properties
* The ''k''-SYG, where ''k'' = 1, is known as the
theta graph
In computational geometry, the Theta graph, or \Theta-graph, is a type of geometric spanner similar to a Yao graph. The basic method of construction involves partitioning the space around each vertex into a set of ''cones'', which themselves p ...
, and is the union of two
Delaunay triangulations.
* For a small
and an appropriate cone axis, the ''k''-SYG gives a supergraph of the
''k''-nearest neighbor graph (''k''-NNG).
For example, in 2D, if we partition the plane around each point into six wedges of equal angles, and pick the cone axes on directions of the cone bisectors, we obtain a ''k''-SYG as a supergraph for the ''k''-NNG.
See also
*
Geometric spanner
A geometric spanner or a -spanner graph or a -spanner was initially introduced as a weighted graph over a set of points as its vertices for which there is a -path between any pair of vertices for a fixed parameter . A -path is defined as a path ...
References
{{Reflist
Computational geometry
Geometric graphs