基于距离的大小为 2 的组

Question

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

我想将这些点分成 N/2 组，每组包含 2 个点（如果 N 是奇数，则每个点包含 3 个）。

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

考虑到算法应该相对较快的限制（这将部署在 API 和运行以响应用户请求），实现此目标的最佳算法是什么？

分组不一定需要 'best' 可能，但最好是确定性的。

Answer 1

首先，我们可以定义一个象限函数：

int quadrant(point a){
    if(a.latitude > 0)
        if(a.longitude > 0) return 1;
        else                return 2;
    else
        if(a.longitude < 0) return 3;
        else                return 4;
}

然后我们可以这样对点进行排序：

bool comparison(point a, point b){
    if (quadrant(a) == quadrant(b)){
        if(a.longitude > b.longitude) return true;
        else return a.longitude > b.longitude;
    else 
        return quadrant(a) < quadrant(b);
}

象限功能就像笛卡尔平面一样，可以帮助您将点放在一起。

基于这样的比较的排序将帮助您将附近的点组合在一起，因此您可以成对 (a1,a2), (a3,a4), ..., (an-1, an)并且需要 O(N lg(N)) 时间。

如果你更好地对待相邻的象限或者做更多的逻辑，你可以优化一点，但这是一个好的开始。

Answer 2

计算中心。

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

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

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

基于距离的大小为 2 的组

Groups of size 2 based on distance

algorithm

cluster-analysis

k-means