这是一个O(n^2 log n)-时间算法仅二维。我将描述更高维度中出现的问题。
令 S 为具有整数坐标的点的集合。对于 S 中的每个点 o，构造非零向量集 V(o) = {p - o | p in S - {o}} 并测试 V(o) 是否包含线性时间内的两个正交向量，如下所示。
方法一：将每个向量(x, y)标准化为(x/gcd(x, y), y/gcd(x, y))，其中|gcd(x, y)|是除以 x 和 y 的最大整数，其中如果 y 为负，则 gcd(x, y) 为负；如果 y 为正，则 gcd(x, y) 为正；|x|如果 y 为零。 （这与用最低项表示分数非常相似。）关于二维的关键事实是，对于每个非零向量，恰好存在一个与该向量正交的规范向量，特别是 (-y, x) 的规范化。将 V(o) 中每个向量的规范化插入到集合数据结构中，然后对于 V(o) 中的每个向量，在该数据结构中查找其规范正交配对。我假设 gcd 和/或 set 操作需要时间 O(log n)。
方法2：在向量上定义比较器，如下所示。给定向量(a, b), (c, d), write (a, b) < (c, d)当且仅当
s1 s2 (a d - b c) < 0,
where
s1 = -1 if b < 0 or (b == 0 and a < 0)
1 otherwise
s2 = -1 if d < 0 or (d == 0 and c < 0)
1 otherwise.
使用此比较器对向量进行排序。 （这与比较分数非常相似a/b with c/d.) 对于 V(o) 中的每个向量 (x, y)，二分搜索其正交配对 (-y, x)。
在三维空间中，沿 z 轴与单位向量正交的向量集是整个 x-y 平面，而规范化的等效方法无法将该平面中的所有向量映射到一个正交配合。
