On the complexity of closest pair via polar-pair of point-sets

DOI10.4230/LIPICS.SOCG.2018.28MaRDI QIDQ5115796zbMATH OpenOpenAlexFDO

Authors Roee David, C. S. Karthik, B. Laekhanukit

Publication date 18 August 2020

Full work available at URL https://doi.org/10.4230/LIPIcs.SoCG.2018.28

zbMATH Keywords

sphericityclosest paircontact dimensionfine-grained complexity

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 4074476 (Why is no real title available?)
• scientific article; zbMATH DE number 3569833 (Why is no real title available?)
• scientific article; zbMATH DE number 3597592 (Why is no real title available?)
• scientific article; zbMATH DE number 3307331 (Why is no real title available?)
• A few applications of negative-type inequalities
• A new algorithm for optimal 2-constraint satisfaction and its implications
• A simple randomized sieve algorithm for the closest-pair problem
• Automata, Languages and Programming
• Class of constructive asymptotically good algebraic codes
• Computational Complexity
• Contact patterns of equal nonoverlapping spheres
• Dispersed points and geometric embedding of complete bipartite graphs
• Embedding into rectilinear spaces
• Equilateral dimension of the rectilinear space
• Equilateral sets in \(l_p^n\)
• Extensions of Lipschitz mappings into a Hilbert space
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Hardness of approximate nearest neighbor search
• Lower Bounds for Algebraic Computation Trees of Functions with Finite Domains
• Monotone maps, sphericity and bounded second eigenvalue
• Multidimensional divide-and-conquer
• On the contact dimensions of graphs
• On the difference between closest, furthest, and orthogonal pairs: nearly-linear vs barely-subquadratic complexity
• Space graphs and sphericity

Cited in

(7)

• On the complexity of closest pair via polar-pair of point-sets
• Two-dimensional closest pair problem: a closer look
• On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
• Maintaining the minimal distance of a point set in polylogarithmic time
• A note concerning the closest point pair algorithm.
• On closest pair in Euclidean metric: monochromatic is as hard as bichromatic
• 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)