Urquhart graph
Encyclopedia
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
.
The Urquhart graph was described by , who suggested that removing the longest edge from each Delaunay triangle would be a fast way of constructing the relative neighborhood graph
(the graph connecting pairs of points p and q when there does not exist any third point r that is closer to both p and q than they are to each other). Since Delaunay triangulations can be constructed in time O(n log n), the same time bound holds for the Urquhart graph as well. Although it was later shown that the Urquhart graph is not exactly the same as the relative neighborhood graph, it can be used as a good approximation to it. The problem of constructing relative neighborhood graphs in O(n log n) time, left open by the mismatch between the Urquhart graph and the relative neighborhood graph, was solved by .
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
, the Urquhart graph of a set of points in the plane, named after Roderick B. Urquhart, is obtained by removing the longest edge
Edge (geometry)
In geometry, an edge is a one-dimensional line segment joining two adjacent zero-dimensional vertices in a polygon. Thus applied, an edge is a connector for a one-dimensional line segment and two zero-dimensional objects....
from each triangle
Triangle
A triangle is one of the basic shapes of geometry: a polygon with three corners or vertices and three sides or edges which are line segments. A triangle with vertices A, B, and C is denoted ....
in the Delaunay triangulation
Delaunay triangulation
In mathematics and computational geometry, a Delaunay triangulation for a set P of points in a plane is a triangulation DT such that no point in P is inside the circumcircle of any triangle in DT. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the...
.
The Urquhart graph was described by , who suggested that removing the longest edge from each Delaunay triangle would be a fast way of constructing the relative neighborhood graph
Relative neighborhood graph
In computational geometry, the relative neighborhood graph is an undirected graph defined on a set of points in the Euclidean plane by connecting two points p and q by an edge whenever there does not exist a third point r that is closer to both p and q than they are to each other...
(the graph connecting pairs of points p and q when there does not exist any third point r that is closer to both p and q than they are to each other). Since Delaunay triangulations can be constructed in time O(n log n), the same time bound holds for the Urquhart graph as well. Although it was later shown that the Urquhart graph is not exactly the same as the relative neighborhood graph, it can be used as a good approximation to it. The problem of constructing relative neighborhood graphs in O(n log n) time, left open by the mismatch between the Urquhart graph and the relative neighborhood graph, was solved by .