Dominance Product and High-Dimensional Closest Pair under $L_{\infty }$

Abstract

Given a set $S$ of $n$ points in ${\mathbb{R}}^d$, the Closest Pair problem is to find a pair of distinct points in $S$ at minimum distance. When $d$ is constant, there are efficient algorithms that solve this problem, and fast approximate solutions for general $d$. However, obtaining an exact solution in very high dimensions seems to be much less understood. We consider the high-dimensional $L_{\infty }$ Closest Pair problem, where $d=n^r$ for some $r>0$, and the underlying metric is $L_{\infty }$. We improve and simplify previous results for $L_{\infty }$ Closest Pair, showing that it can be solved by a deterministic strongly-polynomial algorithm that runs in $O(DP(n,d)\log n)$ time, and by a randomized algorithm that runs in $O(DP(n,d))$ expected time, where $DP(n,d)$ is the time bound for computing the {\em dominance product} for $n$ points in ${\mathbb{R}}^d$. That is a matrix $D$, such that $D[i,j]=|\{k\mid p_i[k]\le p_j[k]\}|$; this is the number of coordinates at which $p_j$ dominates $p_i$. For integer coordinates from some interval $[-M,M]$, we obtain an algorithm that runs in $\tilde{O}\left(\min \{M{n}^{\omega (1,r,1)},DP(n,d)\}\right)$ time, where $\omega (1,r,1)$ is the exponent of multiplying an $n\times n^r$ matrix by an $n^r\times n$ matrix. We also give slightly better bounds for $DP(n,d)$, by using more recent rectangular matrix multiplication bounds. Computing the dominance product itself is an important task, since it is applied in many algorithms as a major black-box ingredient, such as algorithms for APBP (all pairs bottleneck paths), and variants of APSP (all pairs shortest paths).