On finding a large number of 3D points with a small diameter

Given a set S of n   points in R3R3, we wish to decide whether S has a subset of size at least k with Euclidean diameter at most r. It is unknown whether this decision problem is NP-hard. The two closely related optimization problems, (i) finding a largest subset of diameter at most r, and (ii) finding a subset of the smallest diameter of size at least k  , were recently considered by Afshani and Chan. For maximizing the size, they presented several polynomial-time algorithms with constant approximation factors, the best of which has a factor of π/arccos13<2.553. For maximizing the diameter, they presented a polynomial-time approximation scheme. In this paper, we present improved approximation algorithms for both optimization problems. For maximizing the size, we present two algorithms: the first one improves the approximation factor to 2.52.5 and the running time by an O(n)O(n) factor; the second one improves the approximation factor to 2 and the running time by an O(n2)O(n2) factor. For minimizing the diameter, we improve the running time of the PTAS from O(nlogn+2O(1/ε3)n)O(nlogn+2O(1/ε3)n) to O(nlogn+2O(1/(ε1.5logε))n)O(nlogn+2O(1/(ε1.5logε))n).