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.

Improve this question
$\endgroup$
3
  • $\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
    Commented Jun 26, 2015 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
    Commented Jun 26, 2015 at 16:40
  • $\begingroup$ @WillBrian: Nice observation re electrons on a sphere. $\endgroup$
    – Joseph O'Rourke
    Commented Jun 26, 2015 at 18:58

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Can you prove the greedy algorithm is optimal here? I don't see why this should be the case. $\endgroup$
    – Kimball
    Commented Jun 26, 2015 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
    Commented Jun 26, 2015 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
    Commented Jun 27, 2015 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):

         

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .