Sphere-of-Influence Graphs

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

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)

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.
Send