Good approximations for the relative neighbourhood graph
D. V. Andrade, and L. H. Figueiredo
Proceedings of 13th Canadian Conference on Computational Geometry, 2001, pp. 25-28.

Abstract: The Urquhart graph of a set of points in the plane is obtained by removing the longest edge from each triangle in the Delaunay triangulation. We show experimental evidence that the Urquhart graph is a good approximation for the relative neighbourhood graph in the sense tht it contains few additional edges. For random samples, the Urquhart graph is typically only about 2% larger than the relative neighbourhood graph, and thus may serve equally well for computational morphology tasks.

[full text pdf]

Last Updated on January 3, 2006