Cone-Based Graphs

random seed

50

number of points

6

number of cones

6

method

Yao

edge directions

Arrow

Line

In graph theory, a spanner graph has the property that the length of a shortest path between vertices is no greater than a constant times the spatial distance between the vertices. Cone-based graphs are geometric graphs defined for points in the plane. The space around each point is partitioned into a fixed number

k

of equiangular cones, and a nearest neighbor is selected in each cone. These graphs are known to be spanners for certain values of

k

. Various types of cone-based graphs differ in the way the nearest neighbor is defined.

This Demonstration generates the cone-based graphs of types "Yao," "Theta," and "HalfTheta" for a random plane point set. These graphs are parameterized by an integer value between 3 and 10, representing the number of cones, and include at most 1 outgoing edge per cone. Their sparse variants "YaoYao," "ThetaTheta," and "HalfThetaTheta" include at most 1 incoming edge per cone, in addition to the outgoing edge.