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.