The relative neighbourhood graph of a finite planar set

By G. Toussaint. 1980

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Evaluation & Benchmarks

Citations in the corpus

Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (2016, methodology): “When the number of candidates is large enough the heuristic allows getting the exact relative neighborhood graph [46] as a subgraph, a minimal subgraph of the Delaunay graph deducible by using only the distances between the nodes.”
A survey on position-based routing in mobile ad hoc networks (2001, methodology): “In order to construct a connected planar subgraph of the graph formed by the nodes in the ad hoc network, a wellknown mechanism [32] is employed: an edge between two nodes A and B is included in the graph only if the intersection of the two circles with radii equal to the distance between A and B ar”
Coverage in wireless ad-hoc sensor networks (2002, background): “Toussaint and Jaromczyk [11], [12] gave the first definition of the relative neighborhood graph to study the pattern recognition.”
A cone-based distributed topology-control algorithm for wireless multi-hop networks (2005, methodology): “Relative neighborhood graphs [24] and their relatives (such as Gabriel graphs, or Gβ graphs [10]) are similar in spirit to the graphs produced by the cone-based algorithm.”
A survey on routing algorithms for wireless Ad-Hoc and mesh networks (2012, unknown): “sect using one of the well-known planar graphs such as Gabriel graph (GG) [39] or Relative Neighborhood Graph (RNG)(11) [111].”
Localized minimum-energy broadcasting in ad-hoc networks (2003, methodology): “In our localized approach, we use the relative neighborhood graph (RNG) [23].”
Asymptotically optimal geometric mobile ad-hoc routing (2002, background): “Often the intersection between the UDG and the Relative Neighborhood Graph (RNG [24]) or the Gabriel Graph (GG [8]), respectively, have been proposed.”
Large Scale Nearest Neighbors Search Based on Neighborhood Graph (2013, methodology): “Neighborhood graph method: The neighborhood graph method organizes the data with a graph structure to connect data points, for example, Delaunay graph [20], relative neighborhood graph [21], and KNN graph [22].”
Query-driven iterated neighborhood graph search for large scale indexing (2012, unknown): “…a tree structure hierarchically organizing subspaces or subsets of data points, it organizes the data with a graph structure to connect data points, for example, Delaunay graph in Sa-tree [28], relative neighborhood graph [40], k -NN ( ǫ -NN) graph [32], and degree-reduced neighborhood graph [1].”
Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph (2017, background): “Relative Neighborhood Graphs (RNG) [38] are not designed for the ANNS problem in the first place.”
Modeling and visualization of leaf venation patterns (2005, methodology): “A significant speedup is possible due to two computational geometry theorems: The relative neighborhood graph is a subset of the Delaunay triangulation [Toussaint 1980], and the average degree of a vertex in a Delaunay triangulation is 6 [Okabe et al. 1992].”
The holes problem in wireless sensor networks: a survey (2005, methodology): “GPSR proposes either Relative Neighborhood Graph(RNG) [37] or Gabriel Graph(GG) [38] to get a planar network graph with no crossing edges.”
Geographic routing made practical (2005, methodology): “Geographic routing algorithms planarize graphs using two planar graph constructs that meet that requirement: the Relative Neighborhood Graph (RNG) [26] and the Gabriel Graph (GG) [5].”
Ad hoc networks beyond unit disk graphs (2003, background): “For finding planar subgraphs, various constructions of different quality and complexity have been conceived [9, 11, 28].”
XTC: a practical topology control algorithm for ad-hoc networks (2004, background): “GXT C and the Relative Neighborhood Graph of G [ 20 ].”
Graph-theoretic scagnostics (2005, background): “• In a relative neighborhood graph [39], an edge exists between any pair of points p and q for which r is the distance between p and q and the intersection of D(p,r) and D(q,r) contains no points.”
Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks (2001, methodology): “Relative neighborhood graphs [15] and their relatives (such as Gabriel graphs, or Gβ graphs [5]) are similar in spirit to the graphs produced by the cone-based algorithm.”
Approximate nearest neighbor queries in fixed dimensions (1993, methodology): “• To reduce the degree of the graph, we use a pruning scheme similar to the one used in the relative neighborhood graph [13], [21].”