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
gollark: Configuring it isn't very annoying, the language makes decent sense and all, but I have about 10 subdomains and tons of random subpaths with special routing and reverse proxying logic.
gollark: I have about 300 lines of nginx config by now.
gollark: Oh, hmm, 20 according to my out of date list, oh dear.
gollark: I run about 15 random bits of somewhat important software at this point and don't actually have an up to date list.
gollark: For a bit I tried doing a thing where my server config was stored in git and I could just run scripts to recreate it on a new install, but this was too annoying and by now I've accumulated so many arbitrary ad-hoc fixes.

See also

References
  1. "Overlay Networks for Wireless Systems" (PDF).
  2. "Simple Topologies" (PDF).
  3. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.