在平面上给定n个点，如何找到一个等距共线三元组（如果存在）？

Question

显然有一种暴力方法可以解决这个问题，复杂度为O(n^3)。是否有更高效的方法？

- rgs

---

很有可能，是的。或者，也许不是。 - KevinDTimm

你应该更详细地解释问题，并且可能给出一个小例子。 - Sirko

你可能想尝试将这个问题同时发布到计算机科学或者数学 StackExchange上。 - Mr. Llama

Answer 1

一种方法是迭代所有点对，并检查是否存在另一个点恰好位于它们之间的中点。根据点集的表示方式，这应该能够获得比O(n^3)更好的运行时间。

- Henry

---

点集的最有效表示是什么？ - rgs

如果坐标是整数，可以使用哈希表；否则，可能需要使用四叉树。 - Henry

Answer 2

• 使用X，Y值作为键创建所有点（N）的哈希集合。
• 迭代每对点，计算中点并检查它是否存在于哈希集合中（N^2）。

N + N^2 < N^3

这里是一个匆忙创建且未经测试的JavaScript函数示例：

function getESCT(points) {
    var hashset = {};
    points.forEach(function(pt) { hashset[pt.x + "," + pt.y] = pt; });
    for(var i=0; i<points.length; i++) {
        var pt1 = points[i];
        for(var j=0; j<points.length; j++) {
            var pt2 = points[j];
            var key = ((pt1.x + pt2.x) / 2) + "," + ((pt1.y + pt2.y) / 2);
            if(hashset[key]) {
                return hashset[key];
            }
        }
    }
    return null;
}

- Louis Ricci