Preprint A141/2002
Empirically good approximations for the relative neighbourhood graph
Luiz Henrique de Figueiredo | Andrade, Diogo Vieira
Keywords:
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 that 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.