Applications of the Relative Neighbourhood Graph

GODFRIED, T. TOUSSAINT (2014) Applications of the Relative Neighbourhood Graph. In: International Conference on Advances in Computing, Communication and Information Technology CCIT 2014, 01 - 02 June,2014, London, UK.

20140908_101118.pdf - Published Version

Download (1MB) | Preview
Official URL:


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.

Item Type: Conference or Workshop Item (Paper)
Uncontrolled 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.
Depositing User: Mr. John Steve
Date Deposited: 18 May 2019 12:18
Last Modified: 18 May 2019 12:18

Actions (login required)

View Item View Item