A proximity graph is a type of graph where connections (edges) are established between points (vertices) that are considered "close" to each other based on a specific definition of closeness. As stated in the reference, proximity graphs are graphs in which points close to each other by some definition of closeness are connected [6].
Understanding Proximity Graphs
In essence, a proximity graph translates the spatial or relational closeness of data points into a graphical structure. The points in the graph typically represent data instances, geometric locations, or nodes in a network, while the edges signify that two points satisfy a certain proximity criterion.
Key Components
- Points (Vertices): These are the fundamental elements represented in the graph. They can be geometric points in space, data vectors, or any entities for which a notion of distance or similarity can be defined.
- Closeness Definition: This is the rule or metric that determines whether two points are considered "close enough" to be connected. The definition can vary widely depending on the application and the nature of the data.
- Connections (Edges): An edge exists between two points if and only if they meet the specified closeness definition. These edges represent the detected relationships or proximities.
How "Closeness" is Defined
The definition of closeness is the core distinguishing factor between different types of proximity graphs. It's not always just Euclidean distance. Some common ways closeness is defined include:
- Distance Threshold: Connecting points within a certain distance of each other.
- Nearest Neighbors: Connecting each point to its k closest neighbors.
- Geometric Criteria: Using geometric rules based on the positions of points (e.g., based on empty regions or specific shapes formed by the points).
Types of Proximity Graphs
Different definitions of closeness lead to various types of proximity graphs, each with unique properties and applications. Here are a few examples:
- k-Nearest Neighbor Graph (k-NNG): Each point is connected to its k closest neighbors.
- Relative Neighborhood Graph (RNG): An edge exists between two points if no other point is significantly closer to both.
- Gabriel Graph (GG): An edge exists between two points if the disk having these two points as diameter contains no other points.
- Delaunay Triangulation (DT): While not strictly a proximity graph by all definitions, it's a fundamental structure where vertices are connected if they form a triangle such that the circumcircle of the triangle contains no other vertices. This is related to the concept of empty regions.
Applications
Proximity graphs are powerful tools used in various fields, including:
- Data Analysis and Clustering: Identifying clusters of points based on connectivity.
- Pattern Recognition: Finding patterns and relationships in datasets.
- Machine Learning: Constructing kernels or features based on spatial relationships.
- Computer Graphics: Generating meshes and representing spatial data.
- Geographic Information Systems (GIS): Analyzing spatial relationships between locations.
By converting spatial or feature space relationships into a graph structure, proximity graphs allow the application of powerful graph theory algorithms to problems involving neighborhood relationships and spatial organization.
