Semi-Yao graph

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.

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 \theta, meaning the angle of each pair of rays inside a polyhedral cone emanating from the apex is at most \theta, and then p connects to k points of P in each of the polyhedral cones whose projections on the cone axis is minimum.

Properties

See also

References

  1. Rahmati, Zahed (2014). Simple, Faster Kinetic Data Structures (PDF) (Thesis). University of Victoria.
  2. Bonichon, N.; Gavoille, C.; Hanusse, N.; Ilcinkas, D. (2010). "Connections between theta-graphs, Delaunay triangulations, and orthogonal surfaces". Graph Theoretic Concepts in Computer Science. pp. 266–278.
  3. Rahmati, Z.; Abam, M. A.; King, V.; Whitesides, S.; Zarei, A. (2015). "A simple, faster method for kinetic proximity problems". Computational Geometry 48 (4): 342–359. doi:10.1016/j.comgeo.2014.12.002.
  4. Rahmati, Z.; Abam, M. A.; King, V.; Whitesides, S. (2016). "Kinetic k-Semi-Yao Graph and its Applications". Computational Geometry.
This article is issued from Wikipedia - version of the Wednesday, January 13, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.