如何划分二维点集为两个子集以最大化各子集内最近点对距离

这个需求属于最大化最小间距的2簇聚类问题，有成熟的可落地算法，核心基于最小生成树（MST）实现，步骤如下：

• 首先计算所有二维点对的欧氏距离，构造无向完全图，边的权值就是对应点对的距离。
• 对上述完全图生成最小生成树，二维点场景下可以用优化版的Prim或者Kruskal算法，时间复杂度可以做到O(n log n)。
• 找到最小生成树里权值最大的边，直接切断这条边，得到的两个连通分量就是满足要求的最优划分结果。

原理说明：你的优化目标是让两个子集各自内部的最近点对距离尽可能大，本质是找最大的阈值d，使得所有距离小于d的点对都不会被分到同一个子集。最小生成树的最大边切割刚好满足这个约束：切割后两个分量内部的所有边权都不超过这条最大边的权值，跨分量的边权都不小于这条边的权值，最终得到的两个子集内部最近点对距离的最小值是所有划分方案里最大的。

如果最小生成树里有多个权值相同的最大边，任选一条切断即可，最终的优化目标值不会有差异。

内容的提问来源于stack exchange，提问作者nickponline