Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Closest Pair:
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