algorithm - 基于距离的大小为 2 的组

Question

我有一个包含数千个长度为 N 的点的列表，每个点都有纬度和经度。

我想将这些点分为 N/2 组，每组包含 2 个点(如果 N 是奇数，则一个将有 3 个)。

这个分组的目的是最小化两点之间的距离。我们可以将每组的误差视为平方点之间的距离。以及所有组的总误差总和。

鉴于算法应该相对较快的限制(这将部署在 API 上并运行以响应用户请求)，实现此目标的最佳算法是什么？

分组不一定需要尽可能“最好”，但最好是确定性的。

Answer 1

计算中心。

按距中心的距离对点进行排序。

按降序，选择下一个未匹配点并将其与最近的未匹配邻居配对。您可以使用三角不等式来保持候选者较小。

对于索引，这种贪婪方法是 O(n log n) 否则 O(n^2)。这可能不是最好的结果，但对于这段运行时间来说应该相当不错了。预排序避免了真正糟糕的情况(只要中心不是太不平衡)。