Random Graphs for Statistical Pattern Recognition

DAVID J. MARCHETTE, PhD, is a researcher at the Naval Surface Warfare Center in Dahlgren, Virginia, where he investigates computational statistics and pattern recognition, primarily as it applies to image processing, automatic target recognition, and computer security. He is also an adjunct professor at George Mason University and a lecturer at Johns Hopkins University.

Preface. 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 (alpha,beta) 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.