I have a set of k n-dimensional points:

P1(x11, x12, ..., x1n), P2(x21, x22, ..., x2n), ..., Pk(xk1, xk2, ..., xkn).

A distance D(Pa, Pb) is defined between any two points, which satisfy usual properties:

  1. D(Pa, Pb) >= 0
  2. D(Pa, Pb) = 0 <=> Pa = Pb
  3. D(Pa, Pb) = D(Pb, Pa)
  4. D(Pa, Pc) ≤ D(Pa, Pb) + D(Pb, Pc)

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:

ⱯPa ƎB(C) ∈ β => D(Pa, 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.


k = 5, n = 2, R = 2, D(Pa, Pb) = euclidean distance on a plane
P1(0,0), P2(1,1), P3(4.5, 4), P4(-4, 1), P5(4,4),

B1(0.5, 0.5) (contains first two points), B2(-4,1) (contains only 4th point), B3(4,4) (contains 3rd and 5th points)


migrated from programmers.stackexchange.com Oct 18 '15 at 23:42

This question came from our site for professionals, academics, and students working within the systems development life cycle.

  • $\begingroup$ Yes, I need minimal number of balls. I would want to say that balls should not intersect, but it seems that there would be cases when the problem would be unsolvable. Probably then - minimal number of non-intersecting balls with radius not more than R. Clustering seems to be what I need, thanks! $\endgroup$ – xaxa Oct 15 '15 at 13:56

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy