Yao graph

In computational geometry, the Yao graph, named after Andrew Yao, is a kind of geometric spanner, a weighted undirected graph connecting a set of geometric points with the property that, for every pair of points in the graph, their shortest path has a length that is within a constant factor of their Euclidean distance.

The basic idea underlying the two-dimensional Yao graph is to surround each of the given points by equally spaced rays, partitioning the plane into sectors with equal angles, and to connect each point to its nearest neighbor in each of these sectors.[1] Associated with a Yao graph is an integer parameter k ≥ 6 which is the number of rays and sectors described above; larger values of k produce closer approximations to the Euclidean distance.[2] The stretch factor is at most , where is the angle of the sectors.[3] The same idea can be extended to point sets in more than two dimensions, but the number of sectors required grows exponentially with the dimension.

Andrew Yao used these graphs to construct high-dimensional Euclidean minimum spanning trees.[3]

Software for drawing Yao graphs

See also

References

  1. ^ "Overlay Networks for Wireless Systems" (PDF). Archived from the original (PDF) on November 20, 2021. Retrieved March 23, 2011.
  2. ^ "Simple Topologies" (PDF).
  3. ^ a b Yao, A. C. (1982), "On constructing minimum spanning trees in k-dimensional space and related problems", SIAM Journal on Computing, 11 (4): 721–736, CiteSeerX 10.1.1.626.3161, doi:10.1137/0211059.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.