Gold, Omer ;
Sharir, Micha
Dominance Product and HighDimensional 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 highdimensional 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 stronglypolynomial 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 dominance product for n points in \mathbb{R}^d.
That is a matrix D, such that
D[i,j] = \bigl \{k \mid p_i[k] \leq p_j[k]\} \bigr; 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\{Mn^{\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 blackbox ingredient, such as algorithms for APBP (all pairs bottleneck paths),
and variants of APSP (all pairs shortest paths).
BibTeX  Entry
@InProceedings{gold_et_al:LIPIcs:2017:8226,
author = {Omer Gold and Micha Sharir},
title = {{Dominance Product and HighDimensional Closest Pair under L_infty}},
booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages = {39:139:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770545},
ISSN = {18688969},
year = {2017},
volume = {92},
editor = {Yoshio Okamoto and Takeshi Tokuyama},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8226},
URN = {urn:nbn:de:0030drops82268},
doi = {10.4230/LIPIcs.ISAAC.2017.39},
annote = {Keywords: Closest Pair, Dominance Product, L_infty Proximity, Rectangular Matrix Multiplication}
}
2017
Keywords: 

Closest Pair, Dominance Product, L_infty Proximity, Rectangular Matrix Multiplication 
Seminar: 

28th International Symposium on Algorithms and Computation (ISAAC 2017)

Issue date: 

2017 
Date of publication: 

2017 