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

arXiv: https://arxiv.org/abs/1608.03245 · HTML: https://mlsanity.com/paper/1608.03245/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Aug 2016.

## Built on by (most cited first, 2 of 2)

- [Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics](https://mlsanity.com/paper/2111.10912/) (2021)
- [On Complexity of 1-Center in Various Metrics](https://mlsanity.com/paper/2112.03222/) (2021)

## Abstract (arXiv)

Every graph G can be represented by a collection of equi-radii spheres in a d-dimensional metric Delta 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 Delta 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 Kn,n in various Lp-metrics and consequently connect the complexity of the monochromatic closest pair and bichromatic closest pair problems.