Dominance product and high-dimensional closest pair under L_

DOI10.4230/LIPICS.ISAAC.2017.39zbMATH Open1457.68291arXiv1605.08107OpenAlexW2963852036MaRDI QIDQ5136258FDOQ5136258

Authors: Omer Gold, Micha Sharir 

Publication date: 25 November 2020

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_{i}nfty$ Closest Pair problem, where $d=n^r$ for some $r>0$, and the underlying metric is $L_{i}nfty$. We improve and simplify previous results for $L_{i}nfty$ Closest Pair, showing that it can be solved by a deterministic strongly-polynomial algorithm that runs in $O(DP(n,d)logn)$ 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 $$; 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 $ildeOleft(minM{n}^{omega(1,r,1)},,DP(n,d)ight)$ time, where $omega(1,r,1)$ is the exponent of multiplying an $nimes{n}^r$ matrix by an $n^{r}imesn$ 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).

Full work available at URL: https://arxiv.org/abs/1605.08107

Recommendations

• Automata, Languages and Programming
• Exact \(L_{\infty}\) nearest neighbor search in high dimensions
• scientific article; zbMATH DE number 794264
• Approximate closest-point queries in high dimensions
• Approximate \(k\)-closest-pairs in large high-dimensional data sets

zbMATH Keywords

closest pairrectangular matrix multiplication\(L_\infty\) proximitydominance product

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

• Powers of tensors and fast matrix multiplication
• Multidimensional divide-and-conquer
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• Title not available (Why is that?)
• Multiplying matrices faster than coppersmith-winograd
• Computing dominances in \(E^ n\)
• The complexity of selection and ranking in X+Y and matrices with sorted columns
• Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
• Fast rectangular matrix multiplication and applications
• Title not available (Why is that?)
• The fast Johnson-Lindenstrauss transform and approximate nearest neighbors
• How good is the information theory bound in sorting?
• Title not available (Why is that?)
• Automata, Languages and Programming
• Title not available (Why is that?)
• Geometric applications of a randomized optimization technique
• Title not available (Why is that?)
• A note on Rabin's nearest-neighbor algorithm
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (5)

• On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
• On the Complexity of Closest Pair via Polar-Pair of Point-Sets
• Brief Announcement: Hamming Distance Completeness and Sparse Matrix Multiplication.
• Hamming Distance Completeness
• Automata, Languages and Programming

This page was built for publication: Dominance product and high-dimensional closest pair under \(L_\infty\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136258)