Random Graphs for Statistical Pattern Recognition

Acknowledgments.

1. Preliminaries.

1.1 Graphs and Digraphs.

1.2 Statistical Pattern Recognition.

1.3 Statistical Issues.

1.4 Applications.

1.5 Further Reading.

2. Computational Geometry.

2.1 Introduction.

2.2 Voronoi Cells and Delaunay Triangularization.

2.3 Alpha Hulls.

2.4 Minimum Spanning Trees.

2.5 Further Reading.

3. Neighborhood Graphs.

3.1 Introduction.

3.2 Nearest-Neighbor Graphs.

3.3 k-Nearest Neighbor Graphs.

3.4 Relative Neighborhood Graphs.

3.5 Gabriel Graphs.

3.6 Application: Nearest Neighbor Prototypes.

3.7 Sphere of Influence Graphs.

3.8 Other Relatives.

3.9 Asymptotics.

3.10 Further Reading.

4. Class Cover Catch Digraphs.

4.1 Catch Digraphs.

4.2 Class Covers.

4.3 Dominating Sets.

4.4 Distributional Results for C_n,m-graphs.

4.5 Characterizations.

4.6 Scale Dimension.

4.7 (α,β) Graphs

4.8 CCCD Classification.

4.9 Homogeneous CCCDs.

4.10 Vector Quantization.

4.11 Random Walk Version.

4.12 Further Reading.

5. Cluster Catch Digraphs.

5.1 Basic Definitions.

5.2 Dominating Sets.

5.3 Connected Components.

5.4 Variable Metric Clustering.

6. Computational Methods.

6.1 Introduction.

6.2 Kd-Trees.

6.3 Class Cover Catch Digraphs.

6.4 Cluster Catch Digraphs.

6.5 Voroni Regions and Delaunay Triangularizations.

6.6 Further Reading.

References.

Author Index.

Subject Index.