We extend the planar results of Chang et al. (1992) to higher dimensions, and show that given a set A of 2n points in d-space it is possible to compute a Euclidean bottleneck matching of A in roughly O(n1.5) time, for d≤6, and in subquadratic time, for any constant d>6. If the underlying norm is L∞, then it is possible to compute a bottleneck matching of A in O(n1.5 log0.5 n) time, for any constant d≥2.
ASJC Scopus subject areas
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications