Relative neighborhood graphs and their relatives

1992/01/01 by Jerzy W. Jaromczyk, Godfried T. Toussaint · 1 citation
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Data Management and Algorithms #Digital Image Processing Techniques #Computer science #Combinatorics #Artificial intelligence #Theoretical computer science #Mathematics #Discrete mathematics

paper · doi:10.1109/5.163414

openalex publication_date 1992/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

Results of neighborhood graphs are surveyed. Properties, bounds on the size, algorithms, and variants of the neighborhood graphs are discussed. Numerous applications including computational morphology, spatial analysis, pattern classification, and databases for computer vision are described.>

Citations

• Data Structures and Network Algorithms
• Voronoi diagrams—a survey of a fundamental geometric data structure
• Scaling and related techniques for geometry problems
• Combinatorial complexity bounds for arrangements of curves and spheres
• A linear-time algorithm for a special case of disjoint set union
• A quadratic time algorithm for the minmax length triangulation
• Nearest neighbor pattern classification
• On the shape of a set of points in the plane

Cited by

• Unit distance graph [wikipedia]