Задача такая: дано N точек и для каждой нужно найти ближайшую.
Ясно, что она решается kD-деревом, а эвристики типа проецирования на прямую валятся хорошими тестами.
Быстро работает(и акцептится) такая идея

for j = 1..n
  num[j] = j
  d[j] = x[j]^2 + y[j]^2
  a[j] = INFINITY

осортируем точки по d

for i = 1..n
  temp1 := i + 1
  temp2 := i - 1
  while (temp1 <= n) and (sqrt(d[temp1]) - sqrt(d[i]) - sqrt(a[num[i]]) < eps){        
    temp3 := squared_distance(x[temp1], y[temp1], x[i], y[i])
    if temp3 < a[num[i]]
      a[num[i]] := temp3
    temp1++
    }

  while (temp2 >= 1) and (sqrt(d[i]) - sqrt(d[temp2]) - sqrt(a[num[i]]) < eps){
    temp3 := squared_distance(x[temp2], y[temp2], x[i], y[i])
    if temp3 < a[num[i]]
      a[num[i]] := temp3
    temp2--
    }

в итоге в массиве а будет квадрат ответа
Вроде ясно, что тут какие-то промежуточные оптимизации, но почему это работает и за сколько?