Transform - Gabriel Network

Given a set of points this operator builds a Gabriel network on that point set by creating new lines to serve as the links. Note: In a classic Gabriel network, the set of points should not include any co-incident points, that is two points which lie exactly at the same location.

 

A Gabriel network is a network where the links are determined by making a pairwise comparison of points in the context of the points around them. We start with a set of points, and consider all possible pairs of points in the set. For each pair of points, we draw a link between them if there are no other points which lie inside a circle whose diameter is the distance between the points and which is defined by the two points.

 

images\sc_gabriel.gif

 

The construction above shows a Gabriel network for a set of five points. Note that if any other pairs of points are considered, the circle defined by them would include at least one other point and thus the link is not drawn.

 

The lines created by this operator will be selected after they are created. It's a good idea to move them to a new drawing to keep the map well organized.

 

Example

 

images\sc_nets_points.gif

 

Using the set of points above, we can create the Gabriel network seen below.

 

images\sc_nets_gabriel.gif

 

Note that a subset of a Gabriel network is created by the Relative Neighborhood Network transform operator as seen below:

 

images\sc_nets_relneigh.gif

 

The Gabriel network is a good way to organize a set of points into a network that maintains a reasonable overall shape of the point set. The relative neighborhood network refines this to create a sparser network that takes greater account of each local point clustering compared to surrounding points. An even sparser network can be created using the Minimum Spanning Tree operator, the results of which are seen below:

 

images\sc_nets_spantree.gif

 

The minimum spanning tree removes loops that are present in the relative neighborhood network and creates a network that uses the minimum total length of links between points that connects all of the points.

 

See Also

 

Relative Neighborhood Network - The transform operator that creates relative neighborhood networks, which are subsets of Gabriel networks. This topic includes a note on characteristics of relative neighborhood networks.

 

Spanning Tree - The transform operator that creates minimum spanning trees.

 

Clusters - Transform operators that use relative neighborhood networks and minimum spanning trees to find clusters.

 

Notes

 

In graph theory, networks are called graphs. When searching Internet for information on these topics try searching for words like "gabriel graph", "relative neighborhood", "graph", "spanning tree", "cluster" and similar. These ideas are applied in an astonishing range of disciplines, from fungal spore distribution patterns to the characterization of finds in archeological sites.

 

The points for the examples above were created by making centroids for provinces in Mexico using the Centroids (Weight) solver. The points and results of the transform operators are shown in a map with a drawing of Mexico as a backdrop. We used the centroids as a source set of points because they are dispersed in a geographically interesting way. There is no meaning to the map of Mexico; however, if we were to place one antenna in the geographic center of each province and then we wished to link the antennas in a network we would likely create and study maps such as these.