The relative neighbourhood graph of a finite planar set

DOI10.1016/0031-3203(80)90066-7MaRDI QIDQ1141155zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Godfried Toussaint

Publication date 1980

Published in Pattern Recognition (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0031-3203(80)90066-7

zbMATH Keywords

algorithmspattern recognitiontriangulationsDelaunay triangulationgeometric probabilityminimal spanning treegeometric complexityrelative neighbourhood graphcomputational perceptiondot patterns

Mathematics Subject Classification ID

Trees (05C05) Structural characterization of families of graphs (05C75) Graph theory (05C99)

Cites work

• An Alternative Definition for "Neighborhood of a Point"
• Computing Dirichlet Tessellations in the Plane
• Divide and conquer for linear expected time
• Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters
• Parallel concepts in graph theory
• Random Minimal Trees
• Random minimal trees
• Triangulation of planar regions with applications

Cited in

(94)

• A strong law of large numbers for random biased connected graphs
• Lens data depth and median
• Structure-activity maps for visualizing the graph variables arising in drug design
• Spatial clustering tests based on the domination number of a new random digraph family
• Complexity, convexity, and unimodality
• Mutual witness proximity drawings of isomorphic trees
• ON THE LONGEST RNG EDGE OF WIRELESS AD HOC NETWORKS
• The expected size of some graphs in computational geometry
• Population-driven urban road evolution dynamic model
• \(\beta\)-skeletons for a set of line segments in \(\mathbb R^2\)
• Random neighborhood graphs as models of fracture networks on rocks: structural and dynamical analysis
• Time-optimum packet scheduling for many-to-one routing in wireless sensor networks
• Rectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors
• Delaunay partitions in \(\mathbb R^n\) applied to non-convex programs and vertex/facet enumeration problems
• Proximity drawings in polynomial area and volume
• Drawing Big Graphs Using Spectral Sparsification
• The \(\gamma\)-neighborhood graph
• Relative neighborhood graphs in three dimensions
• Design/upgrade of a transparent optical network topology resilient to the simultaneous failure of its critical nodes
• Closed rectangle-of-influence drawings for irreducible triangulations
• An O(n log n) plane-sweep algorithm for \(L_ 1\) and \(L_{\infty}\) Delaunay triangulations
• The distribution of the relative arc density of a family of interval catch digraph based on uniform data
• New sequential and parallel algorithms for computing the \(\beta\)-spectrum
• A linear-time construction of the relative neighborhood graph from the Delaunay triangulation
• Proximity graphs: {\(E, \delta\)}, {\(\Delta\)}, {\(\chi\)} and {\(\omega\)}
• A new family of proximity graphs: class cover catch digraphs
• Local solutions for global problems in wireless networks
• A continuous strategy for collisionless gathering
• A simple linear-time algorithm for computing the ring and MST of unimodal polygons
• The use of domination number of a random proximity catch digraph for testing spatial patterns of segregation and association
• Semantic fusion of laser and vision in pedestrian detection
• A survey of constrained classification
• The relative neighborhood graph for mixed feature variables
• Characterizing proximity trees
• The approximate rectangle of influence drawability problem
• The rectangle of influence drawability problem
• Depth functions and mutidimensional medians on minimal spanning trees
• Solving the Euclidean bottleneck biconnected edge subgraph problem by 2- relative neighborhood graphs
• Growing spanning trees in plasmodium machines
• Co-evolution of density and topology in a simple model of city formation
• Position-based routing in wireless ad hoc and sensor networks
• RNG RELAY SUBSET FLOODING PROTOCOLS IN MOBILE AD-HOC NETWORKS
• Comparison of relative density of two random geometric digraph families in testing spatial clustering
• On constructing the relative neighborhood graphs in Euclidean k- dimensional spaces
• Constructing competitive tours from local information
• Not all insertion methods yield constant approximate tours in the Euclidean plane
• Good triangulations yield good tours
• Classification by restricted random walks
• Extension of one-dimensional proximity regions to higher dimensions
• On vertex- and empty-ply proximity drawings
• An investigation of new graph invariants related to the domination number of random proximity catch digraphs
• Odd Yao-Yao graphs are not spanners
• Graph theoretical clustering based on limited neighbourhood sets
• Computing relative neighbourhood graphs in the plane
• The region approach for computing relative neighbourhood graphs in the \(L_ p\) metric
• A linear expected-time algorithm for computing planar relative neighbourhood graphs
• Swarm intelligence for self-organized clustering
• Constructing the relative neighborhood graph in 3-dimensional Euclidean space
• An almost naive algorithm for finding relative neighbourhood graphs in $L_p$ metrics
• On the expected maximum degree of Gabriel and Yao graphs
• Selection of alpha for alpha-hull in \(\mathbb{R}^ 2\)
• A Pre-Processed Cross Link Detection Protocol for geographic routing in mobile ad hoc and sensor networks under realistic environments with obstacles
• Essential constraints of edge-constrained proximity graphs
• Edge density of new graph types based on a random digraph family
• A divide-and-conquer algorithm for constructing relative neighborhood graph
• Solving the Euclidean bottleneck matching problem by \(k\)-relative neighborhood graphs
• Simulated Annealing and Genetic Algorithms in Quest of Optimal Triangulations
• Affine invariant triangulations
• Connectivity of random geometric graphs related to minimal spanning forests
• Coloring certain proximity graphs
• Optimization of the movements of a component placement machine
• Classification using proximity catch digraphs
• A new family of random graphs for testing spatial segregation
• GEOMETRIC PROXIMITY GRAPHS FOR IMPROVING NEAREST NEIGHBOR METHODS IN INSTANCE-BASED LEARNING AND DATA MINING
• Parsimonious hidden Markov models for matrix-variate longitudinal data
• Computing the relative neighborhood graph in the \(L_ 1\) and L//infinity metrics
• Proximity drawings of high-degree trees
• A Continuous Strategy for Collisionless Gathering
• A linear-time construction of the relative neighborhood graph within a histogram
• Minimum weight euclidean matching and weighted relative neighborhood graphs
• Finding the minimum vertex distance between two disjoint convex polygons in linear time
• Fast algorithms for computing \(\beta\)-skeletons and their relatives.
• Intersections with random geometric objects
• Further nonparametric tests for comparing dissimilarity matrices based on the relative neighborhood graph
• A graph-theoretical clustering method based on two rounds of minimum spanning trees
• Weighted \({\mathcal A}\)-shape: A descriptor of the shape of a point set
• Constructing competitive tours from local information
• Relative density of the random \(R\)-factor proximity catch digraph for testing spatial patterns of segregation and association
• Partial dissimilarities with application to clustering
• Shape-faithful graph drawings
• Comparison of proximity measures for a topological discrimination
• Tuned communicability metrics in networks. The case of alternative routes for urban traffic
• 10-Gabriel graphs are Hamiltonian
• Physarum in silicon: the Greek motorways study

This page was built for publication: The relative neighbourhood graph of a finite planar set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1141155)