4
$\begingroup$

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.

Example:

If
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),

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

$\endgroup$

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
2
$\begingroup$

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.

$\endgroup$

Your Answer

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