International Journal of Advances in Computer Science and Its Applications
Author(s) : GODFRIED T. TOUSSAINT
The relative neighborhood graph of a collection of objects assigns an edge to a pair of objects (A, B), provided that no other object is closer to both A and B, than A and B are to each other. This graph was originally proposed for the purpose of extracting the low-level visual perceptual structure of two-dimensional dot patterns. During the past thirty-four years the relative neighborhood graph has been applied to a multiplicity of different disciplines, and sometimes to several problems within a single discipline. This paper provides a review of some of these applications, including: wireless network communications, archaeological network analysis, grid typification in cartography, data mining for geographic information systems, shape analysis, image morphology, polygon decomposition, the extraction of primal sketches in computer vision, the reduction of the size of the training set in instance-based machine learning, the design of non-parametric decision rules, support-vector machines, cluster analysis, manifold learning, the design of nonparametric tests of the independence of dissimilarity matrices, the design of data-depth measures, testing class separability, estimating two-dimensional voids in the cold dark matter universe, multidimensional data-base indexing, image retrieval, adaptive grid generation for solving partial differential equations, clinical case retrieval in health-care systems, modeling road networks in transportation science, modeling leaf venation patterns in biology, plasmodium machines, swarm intelligence, distributed motion coordination, visualizing metabolic reactions in chemistry, tracking defects in crystal structures, and developing visualization tools such as topological zooming as well as Tukey scagnostics.