# Sphere-of-Influence Graphs

Sphere-of-Influence Graphs

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.

S

V

S

N(V)

V

S

V

|V-N(V)|

U

V

U

V

|U-V|≤|V-N(V)|+|U-N(U)|