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
Mauro,
Are there papers/ preprints/ e-prints available on Beta-skeletons? I fell on that concept as being natural (as an interpolation of what revealed to be Delaunay and Gabriel graphs) but then remembered about Delaunay, learned about Gabriel graphs, and then now found Beta-skeletons: are there your idea? And anyway, pointer to material on the math and computation aspects would be most welcome.
Thanks
Charles
You can check this PhD thesis:
“Some computation on Beta-Skeletons”
S. V. Rao, Ph.D. thesis, Indian Inst. of Tech., Kanpur, Dept. of Computer Science & Engineering, Jul 1998
http://www.cse.iitk.ac.in/research/phd/svrao.html