On the Complexity of Closest Pair via Polar-Pair of Point-Sets

2016/08/10 by Roee David, Karthik C. S., David, Roee +3 · 1 citation
Computer Science · Mathematics · #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG) #cs.CC #cs.CG #math.MG

paper · pdf · doi:10.48550/arxiv.1608.03245

The paper was previously titled, "The Curse of Medium Dimension for Geometric Problems in Almost Every Norm"

arxiv created 2018/11/15 · arxiv updated 2018/11/16

Abstract

Every graph G can be represented by a collection of equi-radii spheres in a d-dimensional metric Δ such that there is an edge uv in G if and only if the spheres corresponding to u and v intersect. The smallest integer d such that G can be represented by a collection of spheres (all of the same radius) in Δ is called the sphericity of G, and if the collection of spheres are non-overlapping, then the value d is called the contact-dimension of G. In this paper, we study the sphericity and contact dimension of the complete bipartite graph K_n,n in various L^p-metrics and consequently connect the complexity of the monochromatic closest pair and bichromatic closest pair problems.

Cited by

• Hardness of Median and Center in the Ulam Metric

Related

• On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
• Sphere of Influence Dimension Conjecture 'Almost Proved'
• Complexity of diameter on AT-free graphs is linear
• Identifying contact graphs of sphere packings with generic radii
• Metric dimension of dual polar graphs