这是一个近似的解决方案。由于N如此之大，而M如此之小，那么以下如何：

1. 计算N的凸包
2. 从船体中选择最多M个满足您的最大距离标准的点。
3. 如果第 2 步留下的点少于M点，则从内部选择 1 个点，使其与先前选择的点的距离最大化。
4. 重复步骤 3，直到选中的点数为M

它背后的直觉是，由于N >> M，并且您希望点彼此尽可能远，它们可能会靠近数据的边缘，因此您不妨从船体开始，然后迭代从那里开始工作。

此外，通过从船体开始，您可以将初始搜索从 N 减少到 N ^1/2。

更新

如果上面的步骤 3 和 4 花费的时间太长（因为您正在迭代测试数据集的内部），我又想到了两个想法来加速您的问题。

1. 随机搜索：假设您在步骤 2 中在船体上找到P个点。然后从内部随机抽取M - P个点。在 X 次试验后选择最佳组合。
2. 模拟退火：计算覆盖数据集的最小边界框（不必与轴对齐，可以倾斜）。然后在该边界框上定义一组M个均匀分布的网格点。请注意，这些点不一定与您的任何数据集点一致。然后为每个网格点找到数据集中的k最近邻。遍历每个M x k组合并选择满足您的最大距离标准的组合。换句话说，您使用初始网格作为引导程序来找到一个好的初始解决方案。

数量很大$N$点和一个小子集$M$要进行选择，考虑关于二维问题的连续版本的已知信息可能会有所帮助。

L. Fejes Tóth（“On the sum of distances determined by a pointset”, Acta Math. Acad. Sci. Hungar., 7:397–401, 1956）表明$M$使成对距离之和最大化的圆上的点是通过规则的顶点来实现的$M$-gon 刻在圆圈上。

随后，他 (L. Fejes Tóth, "Über eine Punktverteilung auf der Kugel", Acta Math. Acad. Sci. Hungar., 10:13-19, 1959) 提出了最大化成对距离之和的更困难的问题$M$平面上的点，其直径（最大成对距离）为$1$. 这个问题总体上仍然悬而未决，尽管 Friedrich Pillichshammer 给出了一个上限并表明它对于$M=3,4,5$（“关于欧几里得平面中的极值点分布”，匈牙利数学报，98（4）：311-321，2003）。

这些少数情况表明，这种极值分布的点往往会出现在区域的外围。为了$M=3$解是一个边长的等边三角形$1$. 为了$M=4$其中三个点再次形成一个等边三角形，第四个点位于通过两个点的圆弧的中点，以第三个点为中心。为了$M=5$解是直径为正五边形$1$. 这些都没有通过图形内部呈现点的“分散”。

如果我们希望避免在外围点的主要选择，一个不同的目标很容易被证明是有用的。点之间的最小距离的最大化就是这样一个标准。相关问题已在StackOverflow、Computer Science SE、Math.SE和MathOverflow上提出。

要了解为什么这种方法会在图形内部产生点，请考虑其与包装的粗略等价$M$直径圈$D$一个图里面。这$M$然后，中心是没有两个比距离更近的点$D$. 这个 Math.SE 答案中的图片可能值得一看，它展示了如何最好地在一个正方形中排列十个点。

好的，所以你想从欧几里得平面中给定的 N 个点集合中选择 M 个点，以使所选点的成对距离之和最大，对吗？

标准的本地搜索算法非常快，并且提供了非常好的近似值。运行时间在 N 中是线性的，在 M 中是二次的。它的近似比是 1 - 4/M。这意味着该比率随着 M 的增加而变得更好。例如，对于 M=10，它获得 60% 的最佳值，而对于 M=50，它获得 92% 的最佳值。

该算法也适用于一般维度的欧几里得空间。在这种情况下，问题是 NP 难的。但是在飞机上，是否是NP-hard就不得而知了。

来源是这篇论文。希望这可以帮助！最佳，阿方索

一种解决方案是：

• 在中创建边界矩形$O(n)$时间

• 在这个边界矩形内使M个人工均匀分布的点，一些M比其他的更难。在你的情况下，四个在矩形的角落，一个在中心

• 构建N个输入点的 KD-Tree。$O(n(log(n)))$

• 在 KD-Tree 中查询每个M点以查找最近的邻居。$O(m(log(n)))$时间

整个算法应该是正确的并且有界$O(n(log(n)))$. 唯一棘手的部分是前面所说的人工M点的分布。我认为更大的素数应该是相当困难的。但我认为有有效的算法来解决这个问题。这是相当微不足道的$\sqrt{M} \in \mathbb{N}$，因为那么只需要生成一个网格，并且这些点是网格中心。