2016/05/26 by Omer Gold, Micha Sharir, Gold, Omer +1
Computer Science · #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CG #cs.DS
paper · pdf · doi:10.48550/arxiv.1605.08107
arxiv created 2017/06/24 · arxiv updated 2017/06/27
Given a set S of n points in ℝ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_∞ Closest Pair problem, where d=nr for some r > 0, and the underlying metric is L_∞. We improve and simplify previous results for L_∞ 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 ℝd. That is a matrix D, such that D[i,j] = | \k | pi[k] ≤ pj[k]\ |; this is the number of coordinates at which pj dominates pi. For integer coordinates from some interval [-M, M], we obtain an algorithm that runs in O(min\Mnω(1,r,1), DP(n,d)\) time, where ω(1,r,1) is the exponent of multiplying an n × nr matrix by an nr × 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).