Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > CONTACT DIMENSION:
Reports tagged with Contact Dimension:
TR18-210 | 30th November 2018
Karthik C. S., Pasin Manurangsi

#### On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic

Given a set of $n$ points in $\mathbb R^d$, the (monochromatic) Closest Pair problem asks to find a pair of distinct points in the set that are closest in the $\ell_p$-metric. Closest Pair is a fundamental problem in Computational Geometry and understanding its fine-grained complexity in the Euclidean metric when ... more >>>

ISSN 1433-8092 | Imprint