Is there any (efficient) algorithm to select subset of $M$ points from a set of $N$ points ($M < N$) such that they "cover" most area (over all possible subsets of size $M$)?

I assume the points are in 2D plane.

The naive algorithm is simple, but prohibitive in terms of time complexity:

for each subset of N points
    sum distance between each pair of points in the subset
    remember subset with the maximum sum

I am looking for a more efficient or even approximate method.

Example, here is a plane with some random points in it:

enter image description here

For $M=5$, I expect selecting points like these:

enter image description here

Note the selected points (red) are scattered all over the plane.

I found an article "EFFICIENTLY SELECTING SPATIALLY DISTRIBUTED KEYPOINTS FOR VISUAL TRACKING" which is related to this problem. However, this assumes the points are weighted.

  • 2
    For the case $M=2$ see this from StackOverflow: Algorithm to find points that are furthest apart — better than O(n^2)?. – hardmath Jun 29 '15 at 1:32
  • Unfortunately, $N$ is usually around 1500-5000 and $M$ is like 10-50. – Libor Jun 29 '15 at 1:58
  • Are $M$ and $N$ both fixed, or are you varying $M$ as well (e.g., because you want to maximize the average of distances, in which case increasing $M$ further may yield a decrease)? – Wolfgang Bangerth Jun 29 '15 at 4:05
  • 1
    I strongly suspect this is NP-hard. It closely resembles a max-weight clique problem where the weight of the edge between two vertices is the Euclidean distance between them. (I believe there are practically-effective heuristics known for max-clique. I'm not sure which ones they are.) – tmyklebu Jun 29 '15 at 4:38
  • 1
    @hardmath Sorry that was a typo. I tried to illustrate what I need to achieve. The problem comes from image feature extraction where I need to get only handful of point features but having them scattered over all image because they are used for transform estimation and when they are spatially scattered, the estimation is more stable. Maybe "entropy" is a better measure - I would like to pick $M$ points such that they are all over the place, like a gas in max entropy state. On the other hand, I am trying to avoid the selected points to be clustered. – Libor Jun 29 '15 at 19:38
up vote 11 down vote accepted

Here is an approximate solution. Since N is so large and M is so small, how about the following:

  1. Compute the convex hull of N
  2. Select up to M points from the hull that satisfy your maximum distance criteria.
  3. If Step 2 leaves you with fewer than M points then select 1 point from the interior that maximizes its distance from the previously selected points.
  4. Repeat Step 3 until the number of selected points is M

The intuition behind it is that since N >> M, and you want points as a far away from each other as possible, they will likely be close to the edges of the data, so you might as well start with the hull and then iteratively work your way in from there.

Also, by starting with the hull, you reduce your initial search from N to N1/2.


UPDATE

If steps 3 and 4 above are taking too long (since you're iteratively testing the interior of your dataset) two more ideas occurred to me to speed up your problem.

  1. Randomized Search: Say you found P points on the hull in Step 2. Then randomly draw M-P points from the interior. Select the best set after X trials.
  2. Simulated Annealing: Compute the smallest bounding box that covers your dataset (doesn't have to be aligned with the axes, could be tilted). Then define a set of M uniformly distributed grid points on that bounding box. Note, these points do not necessarily coincide with any of your dataset points. Then for each grid point find the k-nearest neighbors in your dataset. Run through every M x k combination and select the one that satisfies your maximum distance criteria. In other words, you are using the initial grid as a bootstrap to find a good initial solution.
  • Thanks. Maybe a formulated the question wrongly. I am aiming for set of points such that they "cover" most area. I thought just the distance criteria is enough but it looks like something more need to be added. – Libor Jun 29 '15 at 8:49
  • Okay I have updated the question. Your proposed method may work well. I also thought about the greedy version algorithm, that should work like: 1) select random point A, 2) select point B furthest apart from A, 3) select point C furthest apart from both A and B, 4) ... continue until $M$ points are selected. – Libor Jun 29 '15 at 8:58
  • 1
    Perhaps a more formal way of stating your problem is that you want a tessellation of size M that covers N and minimizes the average tessellation facet area? Minimizing the facet areas seems to be a way of spreading the points around and making sure they don't clump together. – dpmcmlxxvi Jun 29 '15 at 16:08
  • Yes. I wanted to avoid using grid because if the points can be accidentaly clustered around grid lines and then they will be clustered in the selection. – Libor Jun 29 '15 at 19:45
  • The one issue with your greedy algorithm you mention is that it will be very sensitive to the initial seed point. Seed growing algorithms (where you start from the inside-out) have that problem. The hull approach I mention will probably be more stable since it works from the outside-in. – dpmcmlxxvi Jun 29 '15 at 19:51

With a very large number $N$ of points and a small subset $M$ to be chosen, it may be helpful to consider what is known about continuous versions of the problem in two-dimensions.

L. Fejes Tóth ("On the sum of distances determined by a pointset", Acta Math. Acad. Sci. Hungar., 7:397–401, 1956) showed that the set of $M$ points on a circle which maximizes the sum of pairwise distances is achieved by vertices of a regular $M$-gon inscribed on the circle.

He subsequently (L. Fejes Tóth, "Über eine Punktverteilung auf der Kugel", Acta Math. Acad. Sci. Hungar., 10:13-19, 1959) posed the more difficult problem of maximizing the sum of pairwise distances for $M$ points in the plane whose diameter (maximum pairwise distance) is $1$. This problem remains open in general, although Friedrich Pillichshammer has given an upper bound and shown it to be sharp for $M=3,4,5$ ("On extremal point distributions in the Euclidean plane", Acta Mathematica Hungarica, 98(4):311-321, 2003).

These few cases suggest that the points of such extremal distributions will tend to occur on the periphery of a region. For $M=3$ the solution is an equilateral triangle with edge length $1$. For $M=4$ three of the points again form an equilateral triangle and the fourth point is located at the midpoint of a circular arc through two of the points, centered on the third point. For $M=5$ the solution is a regular pentagon of diameter $1$. None of these present a "scattering" of points through the interior of a figure.

If we wish to avoid predominating selection of points at the periphery, a different objective is apt to prove useful. The maximization of the minimum distance between points is such a criterion. Related problems have been broached at StackOverflow, at Computer Science SE, at Math.SE, and at MathOverflow.

For some insight into why this approach yields points interior to a figure, consider its rough equivalence to packing $M$ circles of diameter $D$ inside a figure. The $M$ centers are then points no two of which are closer than distance $D$. The picture in this Math.SE Answer will likely be worth a glance, showing how to best arrange ten points in a square.

OK, so you want to select M points from a given set of N points in the Euclidean plane, so that the sum of pairwise distances of the selected points is maximal, correct?

The standard local search algorithm is pretty fast and offers a pretty good approximation. The runtime is linear in N and quadratic in M. Its approximation ratio is 1 - 4/M. This means that the ratio gets better as M increases. For instance, for M=10 it gets 60% the optimal value, and for M=50 it gets 92% the optimal value.

The algorithm works also for Euclidean spaces of general dimension. In this case, the problem is NP-hard. But on the plane, it is not known if it is NP-hard.

The source is this paper. Hope this helps! Best, Alfonso


  • 1
    I have already solved this using "Suppression via Disk Covering" algorithm from the paper "Efficiently selecting spatially distributed keypoints for visual tracking" 2011 18th IEEE International Conference on Image Processing. IEEE, 2011 – Libor Jul 27 '16 at 11:40
  • 1
    Alfonso, please make explicit your affiliation for the suggested paper. – nicoguaro Jul 27 '16 at 23:18

One solution is:

  • Create the bounding rectangle in $O(n)$ time

  • Make M artificial even distributed points inside this bounding rectangle, some M are more difficult than others. In your case four in the corners of the rectangle and one in the center

  • Build a KD-Tree of your N input points. $O(n(log(n)))$

  • Query each of your M points for nearest neighbor in the KD-Tree. $O(m(log(n)))$ time

The whole algorithm should be correct and is bounded to $O(n(log(n)))$. The only tricky part is as said before the distribution of the artificial M points. I assume larger prime numbers should be rather difficult. But I assume there are efficient algorithms for this. It is quite trivial for $\sqrt{M} \in \mathbb{N}$, as then only a grid needs to be generated and the points are the grid centers.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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