Всем добрый день!

Недавно я наткнулся на такую задачу: найти среди данных N точек две, наиболее удалённые друг от друга по сумме разностей абсолютных значений координат в трёхмерном пространстве(N < 10^6). Она решается перебором всех 8 возможных постановок знаков при раскрытии модулей, после чего для каждого случая ищется наибольшее и наименьшее значения в точках, которые потом вычитаются друг из друга, после чего из полученных 8 чисел берётся максимум. Но что делать, если размерность пространства больше 3?

Первый подход к задаче может заключаться в переборе всех пар точек и вычислению манхеттенских расстояний между ними — асимптотика O(K*N^2), где K — размерность пространства. Второй метод(как в решении исходной задачи) — перебрать все 2^K способов раскрытия модулей, для каждого из них найти пару наиболее удалённых точек за 1 проход, после чего из полученных 2^K значений выбрать максимум. Асимптотика — O(K*N*2^K). Однако при K>20 оба этих метода уже не годятся. Собственно меня интересует, есть ли более быстрые способы решить эту задачу? В идеале хотелось бы чего-то вроде O(N*polylog(N)*polynom(K)), но буду рад, если кто-нибудь предложит и что-нибудь промежуточное вроде O(K*N*sqrt(N))