On the Complexity of Closest Pair via Polar-Pair of Point-Sets
From MaRDI portal
Publication:3122310
DOI10.1137/17M1128733zbMath1407.05165arXiv1608.03245OpenAlexW2924398237MaRDI QIDQ3122310
C. S. Karthik, Roee David, Bundit Laekhanukit
Publication date: 20 March 2019
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1608.03245
Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62) Combinatorial complexity of geometric structures (52C45)
Related Items (3)
On closest pair in Euclidean metric: monochromatic is as hard as bichromatic ⋮ Unnamed Item ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Multidimensional divide-and-conquer
- On the contact dimensions of graphs
- Space graphs and sphericity
- Dispersed points and geometric embedding of complete bipartite graphs
- Contact patterns of equal nonoverlapping spheres
- A few applications of negative-type inequalities
- Embedding into rectilinear spaces
- Equilateral sets in \(l_p^n\)
- A simple randomized sieve algorithm for the closest-pair problem
- Monotone maps, sphericity and bounded second eigenvalue
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Extensions of Lipschitz mappings into a Hilbert space
- Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
- Dominance Product and High-Dimensional Closest Pair under L_infty
- Hardness of approximate nearest neighbor search
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- Automata, Languages and Programming
- Class of constructive asymptotically good algebraic codes
- Computational Complexity
- Equilateral dimension of the rectilinear space
This page was built for publication: On the Complexity of Closest Pair via Polar-Pair of Point-Sets
