Proximity Problems

4.1. Low dimensions:

slab, trapezoidal maps, triangulation hierarchies?

4.2. Intermediate dimensions:

kd-trees, range trees, fractional cascading?

4.3. Very high dimensions:

Locality-Sensitive Hashing.

-- TD:

implementation of a k-d tree? range tree? or some application (e.g. Mean-Shift clustering)?