If there is a set of n points in a plan (with known x, y coordinates), can I use a numerical criterion to establish if two points are neighbours, given the definition of a neighbour for Voronoi diagrams or Gabriel graphs?
I am interested in a numerical/ computational criterion, based on x, y coordinates of the p1, p2 points to test if p1 is a neighbour of p2. I am not interested in determining or storing all the neighbours, just a test to verify the neighbouring property.
Of course, the test can involve not only the x, y coordinates of the p1, p2 points but also the other properties of the set (e.g. min or max distances to all the other points).
Or there is another algorithm for constructing a Voronoi neighbouring matrix (a matrix of adjacency) for the set of points?
keywords: Voronoi, adjacency matrix, Gabriel graph,
Delaunay triangulation, neighbouring criterion
Two nodes in the Voronoi diagram are neighbors if they share an edge.
The attached reference makes great suggestions for reading the edges to interpret adjacency.
https://people.sc.fsu.edu/~jburkardt/presentations/voronoi_neighbors.pdf
Consider the case when the points of a straight line connecting two neighboring points belong only to the regions of these two neighboring points. In this case, the adjacent points are the closest to the point lying in the middle of the straight line connecting them, or lying on the boundary separating the corresponding areas.
Dear Morton,
Thank you for your thoughts. The paper you mentioned, explains a good way of constructing the adjacency matrix (according to the Voronoi diagram properties), but I am curious if anyone found a criterion to test if two points may be considered neighbours without constructing the Voronoi diagram.
Or without constructing the polygon edges. Just a simple geometrical criterion which can be computed for two points.
I also studied Okabe's Spatial Tessellations, but I didn't found anything on this matter.
Otherwise, Delaunay tessellations offer a simpler way to find neighbours, considering two vertices are natural neighbours if they are connected by a Delaunay edge (although, to be more precise, in some cases the wright interpretation might require to use the Pitteway triangulation and not the Dalauney). But this solution requires the same amount of calculation, constructing the whole mesh of triangulation for a set of points.
I just wonder if there is another simpler criterion to tell for two points if they are neighbours, regardless of the used tessellation (Dalauney, Pitteway, Voronoi or Gabriel graphs).
Dear Alexander,
Thank you for your answer. But I guess I wasn't explicit enough. I didn't want an observational criterion that is relying on the basic properties of Voronoi diagrams.
I want a simple criterion to be applied on two points, without constructing the tessellation or triangulation for that particular set of points.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs