k-dimensional space, $l_m$ (or $l_\infty$ ) norm

Given $n$ points in metric space, typically $k$ -dimensional space equipped with $l_m$ (or $l_\infty$ ) norm, find a pair of points with the smallest distance between them.

Parameters

$n$ : number of points
$k$ : dimension of space

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 4 of 4 algorithms


Fortune and Hopcroft	1979	$O(kn \log\log n + n 3^k)$	$O(n)$
Rabin' Algorithm	1976	$O(3^k n^2)$	$O(n)$
Bentley; Shamos	1976	$O(kn \log n)$	$O(kn)$
Naive Implementation	1975	$O(kn^2)$	$O(1)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms