3
$\begingroup$

I have $N$ points and I have a distance between every pair of points stored in a 2D matrix. The goal is to find the nearest $K$ points among these $N$ points. "Nearest" means the sum of all distances between the $K$ points is smallest. A brute-force way is to search all combinations of $K$ points from the $N$ points. However, $K \ll N$. For example, $K$ is 5 and $N$ is 100. It is infeasible to search all ${100 \choose 5}$ combinations.

Actually, the distance between points is a metric to measure the difference between elements in the set, so it is better to describe the problem using graph rather than computational geometry.

I have read Clique problem on wiki, but I think the setting is different from my context here.

More info: The elements are probability discrete distributions. The metric here is Hellinger distance en.wikipedia.org/wiki/Hellinger_distance, which is to measure the difference between two probability distributions. I like to find the most similar probability distribution subset from a set.

$\endgroup$
  • $\begingroup$ @Evil I want to find K nearest points from N points. "Nearest" means the K points is "densest" among the N points. The output should be K points. Say K = 5, and N = 100. The sum of distance between (5*4/2) pairs of the 5 points should be the smallest. $\endgroup$ – jackykuo Jul 5 '16 at 18:43
  • $\begingroup$ When you say distance between points is a metric, do you mean metric in the mathematical sense? Do you need an exact solution or does an approximate solution suffice? $\endgroup$ – Solomonoff's Secret Jul 5 '16 at 21:36
  • $\begingroup$ Yes, in mathematical sense, a measuring number. Approximate solution would be fine. $\endgroup$ – jackykuo Jul 5 '16 at 22:01
  • $\begingroup$ When I say "metric in the mathematical sense" I mean this: en.wikipedia.org/wiki/Metric_(mathematics)#Definition $\endgroup$ – Solomonoff's Secret Jul 5 '16 at 22:06
  • $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Jul 6 '16 at 7:59
3
$\begingroup$

This problem does generalize the clique problem.

One example of a metric is the shortest path distance in a connected, unweighted graph $G$, where the distance between vertices $u$ and $v$, $d(u,v)$, is the length of the shortest path between them. There exists a clique of size $K$ in this graph if and only if we can find $K$ points whose distances sum to ${K \choose 2}$.

For finding cliques of size $5$ you can do slightly better than brute force: see this answer. However without more structure on the metric you are interested in it is an open problem to do significantly better.

$\endgroup$
  • $\begingroup$ Thanks for your answer. The elements are probability discrete distributions. The metric here is Hellinger distance en.wikipedia.org/wiki/Hellinger_distance, which is to measure the difference between two probability distributions. I like to find the most similar probability distribution subset from a set. $\endgroup$ – jackykuo Jul 6 '16 at 2:59
  • 2
    $\begingroup$ @jackykuo Jacky, even if it might seem irrelevant to you, it's a good idea to put details about your problem, such as what the points and metric are, into the question. Not only does it help people understand your problem better but someone might find a way to use the details of your problem to provide you with a better answer. $\endgroup$ – Solomonoff's Secret Jul 6 '16 at 14:46
-1
$\begingroup$

If the distances are a metric that would mean if A is close to B, C, D and E, then B, C, D and E should be close to each other. . Unless someone constructed the data to make it hard, the solution ought to be one data point and four of the data points closest to it.

For every point, create a list of all the other points, sorted by distance in ascending order. For each list calculate the sum of distances between the first point and the four nearest; the smallest sum would be your benchmark. Sort the points by this sum in ascending order. You now have everything arranged in an order that would tend to give you small sums of distances.

Now you can do an exhaustive search with shortcuts: You iterate through the first points with the smallest sum first, the second points in order of distance to the first points, etc. Most important that you ignore anything that cannot be optimal. Say your smallest sum of distances so far is 40, and you picked four points with a sum of distances of 26.9, then the fifth point cannot be further than 13.1 away from the first point. If the distances obey the triangular equation then you can take further shortcuts.

Say you have three points with a sum of distances of 7, the second and third points are at distance 2 and 3 from the first point, and the fourth point is at a distance d from the first point (and therefore the fifth at a distance at least d), then the last two points are at least d, d-2, and d-4 away from the first three points, so the sum of distances is at least 7 + 2 (3d - 6) = 6d - 5. So if the sum to beat is 40, we must have 6d - 5 ≤ 40 or d ≤ 7.5. That should seriously restrict the choice of the fourth point.

I'm sure it's possible to construct examples where this doesn't work well, but if you take say the locations of the largest 1000 cities in the world and you want the five closest to each other this would work quite well.

About proof that it gives the correct answer: Well, obviously yes. It does in principle an exhaustive search, except that it orders items in a way that small sums tend to be examined at the start of the search, and we can prune off search branches when it can be proven that they cannot lead to an optimal result. Sorting first means we get good (not optimal) results quickly which make the pruning more effective.

The counter example isn't a counter example. Yes, we will start with sorted lists that start with a point A on the inner n-gon, a few of the neighbouring points on the same n-gon, and some on the outer n-gon which isn't optimal. But that's just the starting point of the search. There was the assumption k << n, which is violated (k = n/2), so it will be harder to prune the search tree effectively. But that's because we don't have k << n.

$\endgroup$
  • 1
    $\begingroup$ Do you have a proof that this provides the optimal answer? I'm skeptical. I doubt this is guaranteed to provide a correct (optimal) answer. Also, beware that the intuition you're using might be badly wrong in higher dimensions; I suspect you're assuming the points come from a 3-dimensional space, but in a high-dimensional space, I don't think the properties you're relying on carry over. $\endgroup$ – D.W. Jul 6 '16 at 1:35
  • 1
    $\begingroup$ I think this is a counter-example. Imagine a regular $n$-gon of side length $L$ centered in a larger regular $n$-gon of side length $2L - \epsilon$. The closest $n$-clique is the inner $n$-gon but each vertex in it is closer to the respective vertex in the outer $n$-gon than its neighbors in the inner $n$-gon. $\endgroup$ – Solomonoff's Secret Jul 6 '16 at 14:49

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.