Нахождение наибольшего набора точек ограниченного диаметра

Для заданных точек в R d и расстояния l найти наибольшее подмножество этих точек, такое, что евклидово расстояние ни одной из них не превышает l .$p_1,\ldots,p_n$$\mathbb{R}^{d}$$l$$l$

В чем сложность этой проблемы?

На графике точек, имеющих ребро, когда расстояние между двумя точками не превышает , задача эквивалентна поиску максимальной клики. Обратное может не иметь места, потому что не каждый граф может быть получен таким способом (примером является звезда K 1 , 7 для d = 2 ). Поэтому связанный вопрос: что известно об этом классе графов?$l$$K_{1,7}$$d=2$

В моей работе с Джеффом Эриксоном «Время ( для двумерной версии этой задачи « Итерированные ближайшие соседи и поиск минимальных многогранников », Диск. Комп. Геом. 11: 321-350, 1994. На самом деле, статья в основном рассматривает двойственную проблему: учитывая количество точек в подмножестве, найдите наименьший возможный диаметр; но он использует проблему, которую вы описываете как подпрограмму. По крайней мере, в то время, когда мы это писали, мы не знали ничего субэкспоненциального для более высоких измерений (хотя, если в подмножестве есть только k точек, экспоненциальную часть можно сделать зависимой от k, а не от $O(n^3\log n)$$k$$k$$n$ используя методы в той же статье).

Аппроксимация довольно проста, если вас интересует наименьшее подмножество с диаметром не более . Алгоритм линейного времени с использованием сеток теперь является «стандартным». Константа, вероятно, будет что-то вроде 2 O ( 1 / ϵ d ) .$(1+\epsilon)l$$2^{O(1/\epsilon^d)}$

Существует некоторая работа по поиску наименьшего шара, содержащего k точек, но проблема диаметра по своей сути сложнее. Чтобы понять почему, хорошей отправной точкой является статья Кларксона-Шора для вычисления диаметра в 3d.

$O(1/\epsilon^2)$