Selecting most scattered points from a set of points

Question

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:

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

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.

Answer 1

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 N^1/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.

Answer 2

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.

Answer 3

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

---

Answer 4

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.