In computer science we often consider models consisting of a bunch of
points (sometimes called Nodes or Vertices) which are joined
to each other by lines (called Edges or Arcs). This collection
of points and the lines between them form what we call a Graph.
Graphs could represent, for example a map. Imagine the points to be cities
and the lines between them to be roads. By looking at the graph you could
tell which cities are directly connected by roads, and which aren't.
The placement of the points and lines determines the type of graph we are
dealing with. For example, if none of the lines cross each other, we say
that the graph is planar. If no lines and points form a 'circle'
in the graph, then we say the graph is a Tree. The Spheres
of Influence Graph is a special kind of graph that obeys the properties
described below.
The spheres of influence graph is constructed as follows:
That, stated as simply as I can put it, is the spheres of influence graph. The applet is also capable of showing the graph formed when each point is connected to its closest neighbour by a line. This is the 'nearest neighbour' graph. This graph is a sub-graph of the spheres of influence graph, which means that all the lines in the nearest neighbour graph are also in the spheres of influence graph. The reverse is not true. The spheres of influence graph has lines that are not in the nearest neighbour graph.
What's a graph for? Well, this graph can be used to extract information
about the points in the graph. The lines (or edges) give a relationship
between the points which is based on their spacial arrangement.
What this means is that by examining the edges in the graph, we can say
someting about the points they connect. In general, a group of points that
lie close will have their circles intersecting, and hence will be connected
into a 'cloud' of points by their edges. The entire spheres of influence
graph may consist of several such 'clouds' of close lying points, the distance
between clouds being larger.
If our points represent some kind of real-world information, the 'clouds'
might allow us to categorize them. All the points in one 'cloud' might belong
to a certain group. For example, each point might be an age and the number
of car-accidents a subject had, so each point forms a is a location in the
(age,accidents) space. The clouds would allow us to identify, for example,
that people between the ages of 20-24 have a tendency to have many car-accidents,
because there is a large cloud of points in that area. When we add a new
point to the graph, representing a new individual, we can tell by which
cloud he joins to which category he belongs.
The applet can plot a few other things that are relevant to the spheres of influence problem. One of these is the graph of nearest neighbours, where each point is connected by a line to the point closest to it. The applet can also draw the circles around each point.