Proximity graphs attempt to represent the overall spatial arrangement of the points in a set. In such a graph, two points are connected by an edge if they are, by a certain measure, “close together”. Specifically, this measure can be: two points are close together if there are no other points in a certain “forbidden region” defined by these two points.

The Gabriel graph (as well as the Relative Neighborhood graph) are particular cases of a continuous family of proximity graphs called Beta-skeletons. In these graphs, the “forbidden region” around two points is defined according to a positive parameter Beta.

Calculating the proximity graph is the first step towards a clustering algorithm. These graphs are used to sparsify the proximity matrix. This is the initial processing for observing an emergence of patterns in the dataset.

Tags: beta-skeletons, information metric, pattern recognition