Relative neighborhood graph

Last updated
The relative neighborhood graph of 100 random points in a unit square. Relative neighborhood graph.svg
The relative neighborhood graph of 100 random points in a unit square.

In computational geometry, the relative neighborhood graph (RNG) is an undirected graph defined on a set of points in the Euclidean plane by connecting two points and by an edge whenever there does not exist a third point that is closer to both and than they are to each other. This graph was proposed by Godfried Toussaint in 1980 as a way of defining a structure from a set of points that would match human perceptions of the shape of the set. [1] [2]

Contents

Algorithms

Supowit (1983) showed how to construct the relative neighborhood graph of points in the plane efficiently in time. [3] It can be computed in expected time, for random set of points distributed uniformly in the unit square. [4] The relative neighborhood graph can be computed in linear time from the Delaunay triangulation of the point set. [5] [6]

Generalizations

Because it is defined only in terms of the distances between points, the relative neighborhood graph can be defined for point sets in any dimension, [1] [7] [8] and for non-Euclidean metrics. [1] [5] [9] [10] Computing the relative neighborhood graph, for higher-dimensional point sets, can be done in time .

The relative neighborhood graph is an example of a lens-based beta skeleton. It is a subgraph of the Delaunay triangulation. In turn, the Euclidean minimum spanning tree is a subgraph of it, from which it follows that it is a connected graph.

The Urquhart graph, the graph formed by removing the longest edge from every triangle in the Delaunay triangulation, was originally proposed as a fast method to compute the relative neighborhood graph. [11] Although the Urquhart graph sometimes differs from the relative neighborhood graph [12] it can be used as an approximation to the relative neighborhood graph. [13]

Related Research Articles

Delaunay triangulation Triangulation method named after Boris Delaunay

In mathematics and computational geometry, a Delaunay triangulation for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P). Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the triangulation; they tend to avoid sliver triangles. The triangulation is named after Boris Delaunay for his work on this topic from 1934.

Convex hull The smallest convex set containing a given set

In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset.

Spanning tree

In the mathematical field of graph theory, a spanning treeT of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree. If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T.

Polygon triangulation

In computational geometry, polygon triangulation is the decomposition of a polygonal area P into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is P.

Euclidean minimum spanning tree

The Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of points in the plane or higher-dimensional Euclidean space. It connects the points by a system of line segments, so that any two points can reach each other along a path through the line segments, and it selects line segments that minimize the sum of the Euclidean distances between directly-connected pairs of points.

Point-set triangulation

A triangulation of a set of points in the Euclidean space is a simplicial complex that covers the convex hull of , and whose vertices belong to . In the plane, triangulations are made up of triangles, together with their edges and vertices. Some authors require that all the points of are vertices of its triangulations. In this case, a triangulation of a set of points in the plane can alternatively be defined as a maximal set of non-crossing edges between points of . In the plane, triangulations are special cases of planar straight-line graphs.

The art gallery problem or museum problem is a well-studied visibility problem in computational geometry. It originates from a real-world problem of guarding an art gallery with the minimum number of guards who together can observe the whole gallery. In the geometric version of the problem, the layout of the art gallery is represented by a simple polygon and each guard is represented by a point in the polygon. A set of points is said to guard a polygon if, for every point in the polygon, there is some such that the line segment between and does not leave the polygon.

In computational geometry, the Theta graph, or -graph, is a type of geometric spanner similar to a Yao graph. The basic method of construction involves partitioning the space around each vertex into a set of cones, which themselves partition the remaining vertices of the graph. Like Yao Graphs, a -graph contains at most one edge per cone; where they differ is how that edge is selected. Whereas Yao Graphs will select the nearest vertex according to the metric space of the graph, the -graph defines a fixed ray contained within each cone and selects the nearest neighbor with respect to orthogonal projections to that ray. The resulting graph exhibits several good spanner properties.

Nearest neighbor search (NNS), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest to a given point. Closeness is typically expressed in terms of a dissimilarity function: the less similar the objects, the larger the function values.

Pseudotriangle

In Euclidean plane geometry, a pseudotriangle (pseudo-triangle) is the simply connected subset of the plane that lies between any three mutually tangent convex sets. A pseudotriangulation (pseudo-triangulations) is a partition of a region of the plane into pseudotriangles, and a pointed pseudotriangulation is a pseudotriangulation in which at each vertex the incident edges span an angle of less than π.

Euclidean shortest path Problem of computing shortest paths around geometric obstacles

The Euclidean shortest path problem is a problem in computational geometry: given a set of polyhedral obstacles in a Euclidean space, and two points, find the shortest path between the points that does not intersect any of the obstacles.

In computational geometry, the Bowyer–Watson algorithm is a method for computing the Delaunay triangulation of a finite set of points in any number of dimensions. The algorithm can be also used to obtain a Voronoi diagram of the points, which is the dual graph of the Delaunay triangulation.

A geometric spanner or a t-spanner graph or a t-spanner was initially introduced as a weighted graph over a set of points as its vertices for which there is a t-path between any pair of vertices for a fixed parameter t. A t-path is defined as a path through the graph with weight at most t times the spatial distance between its endpoints. The parameter t is called the stretch factor or dilation factor of the spanner.

Nearest neighbor graph Type of directed graph

The nearest neighbor graph (NNG) is a directed graph defined for a set of points in a metric space, such as the Euclidean distance in the plane. The NNG has a vertex for each point, and a directed edge from p to q whenever q is a nearest neighbor of p, a point whose distance from p is minimum among all the given points other than p itself.

Godfried Toussaint

Godfried Theodore Patrick Toussaint was a Canadian Computer Scientist, a Professor of Computer Science, and the Head of the Computer Science Program at New York University Abu Dhabi (NYUAD) in Abu Dhabi, United Arab Emirates. He is considered to be the father of computational geometry in Canada. He did research on various aspects of computational geometry, discrete geometry, and their applications: pattern recognition, motion planning, visualization, knot theory, linkage (mechanical) reconfiguration, the art gallery problem, polygon triangulation, the largest empty circle problem, unimodality, and others. Other interests included meander (art), compass and straightedge constructions, instance-based learning, music information retrieval, and computational music theory.

In computational geometry and computer science, the minimum-weight triangulation problem is the problem of finding a triangulation of minimal total edge length. That is, an input polygon or the convex hull of an input point set must be subdivided into triangles that meet edge-to-edge and vertex-to-vertex, in such a way as to minimize the sum of the perimeters of the triangles. The problem is NP-hard for point set inputs, but may be approximated to any desired degree of accuracy. For polygon inputs, it may be solved exactly in polynomial time. The minimum weight triangulation has also sometimes been called the optimal triangulation.

Urquhart graph

In computational geometry, the Urquhart graph of a set of points in the plane, named after Roderick B. Urquhart, is obtained by removing the longest edge from each triangle in the Delaunay triangulation.

Beta skeleton

In computational geometry and geometric graph theory, a β-skeleton or beta skeleton is an undirected graph defined from a set of points in the Euclidean plane. Two points p and q are connected by an edge whenever all the angles prq are sharper than a threshold determined from the numerical parameter β.

In computational geometry, a constrained Delaunay triangulation is a generalization of the Delaunay triangulation that forces certain required segments into the triangulation as edges, unlike the Delaunay triangulation itself which is based purely on the position of a given set of vertices without regard to how they should be connected by edges. It can be computed efficiently and has applications in geographic information systems and in mesh generation.

Greedy geometric spanner

In computational geometry, a greedy geometric spanner is an undirected graph whose vertices represent points in a Euclidean space, and whose edges are selected by a greedy algorithm to make the shortest path distances in the graph approximate the Euclidean distances between pairs of points. The greedy spanner was first described in the PhD thesis of Gautam Das and conference paper and subsequent journal paper by Ingo Althöfer et al. These sources also credited Marshall Bern (unpublished) with the independent discovery of the same construction.

References

  1. 1 2 3 Toussaint, G. T. (1980), "The relative neighborhood graph of a finite planar set", Pattern Recognition, 12 (4): 261–268, doi:10.1016/0031-3203(80)90066-7 .
  2. Jaromczyk, J.W.; Toussaint, G.T. (1992), "Relative neighborhood graphs and their relatives", Proceedings of the IEEE, 80 (9): 1502–1517, doi:10.1109/5.163414 .
  3. Supowit, K. J. (1983), "The relative neighborhood graph, with an application to minimum spanning trees", Journal of the ACM , 30 (3): 428–448, doi:10.1145/2402.322386 .
  4. Katajainen, Jyrki; Nevalainen, Olli; Teuhola, Jukka (1987), "A linear expected-time algorithm for computing planar relative neighbourhood graphs", Information Processing Letters , 25 (2): 77–86, doi:10.1016/0020-0190(87)90225-0 .
  5. 1 2 Jaromczyk, J. W.; Kowaluk, M. (1987), "A note on relative neighborhood graphs", Proc. 3rd Symp. Computational Geometry, New York, NY, USA: ACM, pp. 233–241, doi:10.1145/41958.41983 .
  6. Lingas, A. (1994), "A linear-time construction of the relative neighborhood graph from the Delaunay triangulation", Computational Geometry , 4 (4): 199–208, doi: 10.1016/0925-7721(94)90018-3 .
  7. Jaromczyk, J. W.; Kowaluk, M. (1991), "Constructing the relative neighborhood graph in 3-dimensional Euclidean space", Discrete Applied Mathematics , 31 (2): 181–191, doi: 10.1016/0166-218X(91)90069-9 .
  8. Agarwal, Pankaj K.; Mataušek, Jiří (1992), "Relative neighborhood graphs in three dimensions", Proc. 3rd ACM–SIAM Symp. Discrete Algorithms, pp. 58–65.
  9. O'Rourke, J. (1982), "Computing the relative neighborhood graph in the and metrics", Pattern Recognition, 15 (3): 189–192, doi:10.1016/0031-3203(82)90070-X .
  10. Lee, D. T. (1985), "Relative neighborhood graphs in the -metric", Pattern Recognition, 18 (5): 327–332, doi:10.1016/0031-3203(85)90023-8 .
  11. Urquhart, R. B. (1980), "Algorithms for computation of relative neighborhood graph", Electronics Letters, 16 (14): 556–557, doi:10.1049/el:19800386 .
  12. Toussaint, G. T. (1980), "Comment: Algorithms for computing relative neighborhood graph", Electronics Letters, 16 (22): 860, doi:10.1049/el:19800611 . Reply by Urquhart, pp. 860–861.
  13. Andrade, Diogo Vieira; de Figueiredo, Luiz Henrique (2001), "Good approximations for the relative neighbourhood graph" (PDF), Proc. 13th Canadian Conference on Computational Geometry.