请输入您要查询的百科知识：

　

词条 Semi-Yao graph
释义

  1. Construction

  2. Properties

  3. See also

  4. References

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 , 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, and is the union of two Delaunay triangulations.[2]
  • For a small and an appropriate cone axis, the k-SYG gives a supergraph of the k-nearest neighbor graph (k-NNG).[3][4] 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

References

1. ^{{Cite thesis | last1 = Rahmati | first1 = Zahed | title= Simple, Faster Kinetic Data Structures | publisher = University of Victoria | url= https://cs.uwaterloo.ca/~zrahmati/pub/Rahmati_Zahed_PhD_2014.pdf | year = 2014}}
2. ^{{Cite conference| last1= Bonichon|first1= N.|last2= Gavoille|first2= C.|last3= Hanusse|first3= N.|last4= Ilcinkas|first4= D.| year =2010|title= Connections between theta-graphs, Delaunay triangulations, and orthogonal surfaces|booktitle= Graph Theoretic Concepts in Computer Science|pages= 266–278}}
3. ^{{Cite journal| last1 = Rahmati | first1 = Z. | last2 = Abam| first2 = M. A. | last3 = King | first3 = V.|author3-link=Valerie King | last4 = Whitesides| first4 = S.|author4-link=Sue Whitesides | last5 = Zarei | first5 = A. | title= A simple, faster method for kinetic proximity problems |issue = 4 | journal =Computational Geometry | volume = 48 | pages =342–359 | year = 2015 | doi=10.1016/j.comgeo.2014.12.002| arxiv = 1311.2032}}
4. ^{{Cite journal| last1 = Rahmati | first1 = Z. | last2 = Abam| first2 = M. A. | last3 = King | first3 = V.|author3-link=Valerie King | last4 = Whitesides| first4 = S. |author4-link=Sue Whitesides | title= Kinetic k-Semi-Yao Graph and its Applications| journal =Computational Geometry| volume =77| pages = 10–26 | year = 2016| doi = 10.1016/j.comgeo.2015.11.001 }}

2 : Computational geometry|Geometric graphs
随便看

　

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

　

Copyright © 2023 OENC.NET All Rights Reserved
京ICP备2021023879号 更新时间：2024/9/29 21:34:55