Problem:
- Given a set of points in a metric space (possibly high dimensional), choose a good set of links between points such that a person could follow links to get progressively closer to some point they have in mind without too much backtracking.
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:
- Explore a space of images. Distance metric might be sum of squared difference between images, or something cleverer.
- Explore a space of documents. Distance metric might be based on word frequencies.
- Augment the set of links in a hyperlinked set of documents. Distance metric would be graph distance.
A first attempt:
- Include a link from A to C if there is no point B such that d(B,A) < d(A,C) and d(B,C) < d(A,C). (That is, a link from A to C may be "occluded" by any point in a lens shaped region between A and C.)
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:
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.