On the complexity of closest pair via polar-pair of point-sets
DOI10.4230/LIPICS.SOCG.2018.28zbMATH Open1473.05213OpenAlexW2962832554MaRDI QIDQ5115796FDOQ5115796
Roee David, B. Laekhanukit, C. S. Karthik
Publication date: 18 August 2020
Full work available at URL: https://doi.org/10.4230/LIPIcs.SoCG.2018.28
Recommendations
- On the complexity of closest pair via polar-pair of point-sets
- Dispersed points and geometric embedding of complete bipartite graphs
- Sphericity exceeds cubicity for almost all complete bipartite graphs
- On closest pair in Euclidean metric: monochromatic is as hard as bichromatic
- On the sphericity and cubicity of graphs
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)
Cites Work
- Extensions of Lipschitz mappings into a Hilbert space
- Multidimensional divide-and-conquer
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Computational Complexity
- A simple randomized sieve algorithm for the closest-pair problem
- Title not available (Why is that?)
- Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
- Space graphs and sphericity
- A few applications of negative-type inequalities
- Title not available (Why is that?)
- On the contact dimensions of graphs
- Embedding into rectilinear spaces
- Equilateral sets in \(l_p^n\)
- Equilateral dimension of the rectilinear space
- Class of constructive asymptotically good algebraic codes
- Automata, Languages and Programming
- Contact patterns of equal nonoverlapping spheres
- Title not available (Why is that?)
- Dispersed points and geometric embedding of complete bipartite graphs
- Title not available (Why is that?)
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- Monotone maps, sphericity and bounded second eigenvalue
- Hardness of approximate nearest neighbor search
- Title not available (Why is that?)
Cited In (5)
- On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
- A note concerning the closest point pair algorithm.
- Two-dimensional closest pair problem: a closer look
- Maintaining the minimal distance of a point set in polylogarithmic time
- A DUAL ALGORITHM FOR FINDING A NEAREST PAIR OF POINTS IN TWO POLYTOPES
This page was built for publication: On the complexity of closest pair via polar-pair of point-sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115796)
