Navigation networks



Each point should have a fairly small number of links. Much less than the dimension of the space, which might be high. (This rules out Voronoi diagrams, unfortunately.)

Example applications:

A first attempt:

Note that this is defined purely in terms of the distance metric, and is therefore applicable to any metric space (even funny ones like edit distances).

2D Example:

Source code (python)

Update 27/7/06: David Eppstein tells me this is called a "Relative Neighborhood Graph". A Relative Neighbourhood Graph is a subset of the Delauny Triangulation, and a superset of the Minimum Spanning Tree. The general problem seems to be known as finding "Proximity Graphs".

Turns out that, as I had hoped, it's been shown that the expected number of edges in a Relative Neighbourhood Graph remains of the same order as the number of nodes even in high dimensions.

Update 28/7/06: This is a page that lets you explore a space of common names, based on an edit distance metric.