Sphere-of-Influence Graphs

Requires a Wolfram Notebook System
Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.
Let be a set of vertices chosen from a grid. Given a vertex
in
, let
be the closest neighbor to
in
and draw a circle with center
and radius
. Draw an edge between two vertices
and
if their circles intersect. In other words, connect
and
if
. This gives the sphere-of-influence graph for the given set of vertices.
Contributed by: Edray Herber Goins and Talitha M. Washington (March 2011)
Open content licensed under CC BY-NC-SA
Snapshots
Details
References:
G. T. Toussaint, "A Graph-Theoretic Primal Sketch," Computational Morphology (G. T. Toussaint, ed.), Amsterdam: Elsevier, 1988 pp. 220–260.
M. J. Lipman, "Integer Realizations of Sphere-of-Influence Graphs," Congr. Numer., 91, 1991 pp. 63–70.
Thickness of Sphere-of-Influence Graphs (2007)
Permanent Citation
"Sphere-of-Influence Graphs"
http://demonstrations.wolfram.com/SphereOfInfluenceGraphs/
Wolfram Demonstrations Project
Published: March 7 2011