Один жизнеспособный вариант для малых k будет состоять в том, чтобы повторно использовать ваш алгоритм O(nlogn) для подмножеств исходного набора точек, удаляя точки по мере продвижения.Точнее, сохраните набор точек, которые образовали минимальную пару.Каждый раз, когда вы запрашиваете следующую ближайшую пару, мы запрашиваем следующую ближайшую пару в этих точках и между каждой точкой и остальными исходными точками и выбираем ближе две пары.
Для начала удалите все, кроме одной из этих точек из исходного набора, и рассчитайте ближайшую пару.Повторите это для каждой из точек в этом «минимальном наборе» и сохраните общую ближайшую пару.Это займет O(j*nlogn) время для вычисления, когда «минимальная установка» имеет размер j.
Затем запросите следующую ближайшую пару в этом «минимальном наборе» через find-min (O(1) время) для кучи min-max размера k, которую мы будем строить при добавленииуказывает на наш "минимальный набор".Каждый раз, когда мы добавляем точки к нашему «минимальному набору», мы вычисляем расстояние между каждой точкой в «минимальном наборе» (размер j) и этими (до) 2 новыми точками, вставляем их в нашу мин-макс кучуи затем удалите столько элементов, сколько необходимо, чтобы снова сделать размер кучи k (самое большее 2j элементов) за O(jlogk) раз.
Теперь возьмем более близкую пару из этих двух (удаливиз кучи, если необходимо - O(logk) время), добавьте точки к нашему «минимальному набору» и обновите кучу мин-макс, как описано, и повторите для оставшихся k-j ближайших пар.В целом, это займет O((k^2)nlogn + (k^2)logk + klogk) = O((k^2)(nlogn + logk)) = O((k^2)nlogn) раз.