有效计算一组点可以构造的等边三角形的数量

Question

我有笛卡尔坐标系中各个点的坐标，我需要计算可以在它们上构造的等边三角形的数量。我怎样才能尽可能高效地及时完成这项工作？

我正在用 C 编写代码，并尝试将所有可能的点对之间的距离存储在哈希表中，这样我就不必再次计算距离，但我确信有一个更有效的解决方案。

Answer 1

这是我能想到的最好的：

1. 对于每个点，使用勾股定理计算到所有其他点的距离。这应该会导致

   n(n-1) / 2

   计算，即集合中唯一对的数量。

2. 将信息存储在类似地图的结构中，以距离为键，距离出现的次数为值。

3. 对于出现 3 次或以上的所有距离，计算可能的等边三角形的数量为

   n(n-1)(n-2)/6

   。 （这是“n 选择 k”，其中 k 为 3；另请参阅：二项式系数）。

4. 将所有这些值加在一起即可得到可能的等边三角形的数量。

因此，距离计算本身是该算法表现最差的方面 (

O(n^2)

)。三角形数量的计算最坏的复杂度为

O(n)

。使用不同的数据结构而不是简单的键/值映射，您甚至可以完全放弃此步骤并在计算距离时保留运行总计。