On the difference between closest, furthest, and orthogonal pairs: nearly-linear vs barely-subquadratic complexity

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1709.05282, http://dl.acm.org/citation.cfm?id=3175348

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

On closest pair in Euclidean metric: monochromatic is as hard as bichromatic
Automata, Languages and Programming
Reductions among high dimensional proximity problems
scientific article; zbMATH DE number 1445325
Algorithms for proximity problems in higher dimensions

Cited in

(15)

Fine-grained complexity theory: conditional lower bounds for computational geometry
On closest pair in Euclidean metric: monochromatic is as hard as bichromatic
A new coding-based algorithm for finding closest pair of vectors
On the complexity of closest pair via polar-pair of point-sets
Hamming Distance Completeness
On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
On the complexity of closest pair via polar-pair of point-sets
scientific article; zbMATH DE number 7250154 (Why is no real title available?)
scientific article; zbMATH DE number 7650079 (Why is no real title available?)
Removing additive structure in 3SUM-based reductions
Finer-grained hardness of kernel density estimation
Tensor ranks and the fine-grained complexity of dynamic programming
Improved space-efficient approximate nearest neighbor search using function inversion
(Multivariate) k-SUM as barrier to succinct computation

This page was built for publication: On the difference between closest, furthest, and orthogonal pairs: nearly-linear vs barely-subquadratic complexity

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