Cover points with minimal number of spheres of fixed radius

Question

I have a set of k n-dimensional points:

P¹(x¹₁, x¹₂, ..., x¹_n), P²(x²₁, x²₂, ..., x²_n), ..., P^k(x^k₁, x^k₂, ..., x^k_n).

A distance D(P^a, P^b) is defined between any two points, which satisfy usual properties:

1. D(P^a, P^b) >= 0
2. D(P^a, P^b) = 0 <=> P^a = P^b
3. D(P^a, P^b) = D(P^b, P^a)
4. D(P^a, P^c) ≤ D(P^a, P^b) + D(P^b, P^c)

What is the algorithm to find areas in which these points aggregate?
More specifically, given a radius R find the smallest set β of n-dimensional "balls" B(C) such that every point lies inside at least one of the balls:

ⱯP^a ƎB(C) ∈ β => D(P^a, C) ≤ R

There is definitely more than one solution (in most cases a ball could be moved a little so that it would still contain the points) and probably there is something else I am missing. But I need an algorithm that would provide at least one solution.

Example:

If
k = 5, n = 2, R = 2, D(P^a, P^b) = euclidean distance on a plane
P¹(0,0), P²(1,1), P³(4.5, 4), P⁴(-4, 1), P⁵(4,4),

Then
B¹(0.5, 0.5) (contains first two points), B²(-4,1) (contains only 4th point), B³(4,4) (contains 3rd and 5th points)

Answer 1

Construct a graph. Represent every point by a node and connect two nodes with an edge if the distance of the represented points is $\leq R$.

Then, a minimial clique cover of the graph tells you which points should belong to the same sphere, one per cluster; pick the center of each set as center for the sphere.

Unfortunately, Minimal Clique Cover is NP-hard so no efficient algorithm is known for it. There may be algorithms suitable for your application in the literature, though.

---

Does it get any better? I don't have a proof, but this feels like a clustering problem to me which tend to be NP-hard. You may want to try and apply the ideas of hierarchical clustering.