Approximation and inapproximability results for maximum clique of disc graphs in high dimensions

We prove algorithmic and hardness results for the problem of finding the largest set of a fixed diameter in the Euclidean space. In particular, we prove that if A∗ is the largest subset of diameter r of n points in the Euclidean space, then for every ε>0 there exists a polynomial time algorithm that outputs a set B of size at least |A∗| and of diameter at most . On the hardness side, roughly speaking, we show that unless P=NP for every ε>0 it is not possible to guarantee the diameter for B even if the algorithm is allowed to output a set of size .