5
$\begingroup$

Suppose you had $N$ many fixed points $X_1, X_2, ..., X_N$ in some Euclidean space $R^d$ and from these coordinates you had to choose $n$ many of them ($n \leq N$ also being fixed) to form a subset $S$ that maximizes the function $f(S) = \sum_{(i,j) \in S \times S} ||X_i-X_j||^2$. How would you choose $S$? Note that $||\cdot||$ is the usual Pythagorean norm.

Informally, you are choosing the n points so that they are as 'distant' from each other as possible. Is there a solution to this problem or at least an algorithmic approach to this problem? Solutions to this problem involving different functions that encode the notion of being 'far apart' would interest me as well.

$\endgroup$
  • $\begingroup$ Define the matrix $a_{ij}:=\|X_i-X_j\|$ then you are left with the problem of finding a submatrix of size $n\times n$ with maximal sum. However, I dont know if there exist an efficient algorithm for this. So far I only found solution for the contiguous submatrix problem. $\endgroup$ – user35593 Jun 26 '15 at 6:11
  • 1
    $\begingroup$ If $n$ is much smaller than $N$ and you distribute your $N$ points more or less uniformly on the surface of a sphere, then your question is a variant of the Thomson problem (see en.wikipedia.org/wiki/Thomson_problem). This problem is very hard, and it is only a very special case of your problem. So I think it's probably hopeless to find a nice algorithm that works optimally in every situation. So I think the answers of Weis and O'Rourke (or others like those) are probably as good as you can hope for. $\endgroup$ – Will Brian Jun 26 '15 at 16:40
  • $\begingroup$ @WillBrian: Nice observation re electrons on a sphere. $\endgroup$ – Joseph O'Rourke Jun 26 '15 at 18:58
1
$\begingroup$

You could try to repeatedly remove the vertex, for which the sum of distances to other vertices is minimal, until you are left with S vertices.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Can you prove the greedy algorithm is optimal here? I don't see why this should be the case. $\endgroup$ – Kimball Jun 26 '15 at 16:07
  • 3
    $\begingroup$ It is not always optimal. Consider the case of trying to choose 3 points from the vertices of a regular hexagon. This algorithm will first remove one point A (any one, by symmetry) and then the point opposite A. It will then remove a third point (again, by symmetry it doesn't matter which) to leave a right triangle. But it's easy to compute that a better solution is the equilateral triangle formed by three mutual non-neighbors. $\endgroup$ – Will Brian Jun 26 '15 at 16:15
  • $\begingroup$ @WillBrian nice counterexample! I suspect that there is no efficient solution to the problem because of its relation to clique problems. $\endgroup$ – Manfred Weis Jun 27 '15 at 5:52
1
$\begingroup$

Nice question. Here I just mention an interesting idea used in this GIS StackExchange posting by whuber (William Huber): Find $n$ clusters among your $N$ points, and take the center of those clusters as your $n$ points. As he says, "You can see it's not great (but it's not too bad, either)." Below, $N=1000$ (colored points), $n=200$ (gray points):


         


| cite | improve this answer | |
$\endgroup$

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.