Sphere-of-Influence Graphs

Initializing live version
Download to Desktop

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




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)

Spheres of Influence

The Spheres of Influence Graph

Research Experiences for Undergraduate Faculty

Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.