Abstract: “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 machin”

Keywords: relative neighbourhood graph, Gabriel graph, minimum spanning tree, Urkuhart graph, Delaunay triangulation, proximity graphs, graph theory, computational geometry, image morphology, primal sketch, visual perception, shape analysis, artificial intelligence, support vector machines, machine learning, statistics, wireless networks