# 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