algorithm - 找出超平面下点数的快速算法

Question

给定欧几里德空间中的点，是否有一种快速算法可以计算任意超平面“下方”的点数？快速意味着时间复杂度低于O(n)

预处理或排序点的时间是可以的

而且，即使不是高维，我也想知道是否存在可以在二维空间中使用的

Answer 1

如果您愿意对这些点进行预处理，那么您必须至少访问每个点一次，即 O(n)。如果您考虑将点在哪一侧的测试作为预处理的一部分，那么您将得到一个 O(0) 算法(具有 O(n) 预处理)。所以我不认为这个问题如前所述是有意义的。

尽管如此，我会尝试给出一个有用的答案，即使它不是 OP 所要求的。

选择超平面单位法线和根点。如果平面以参数形式给出

(P - O).N == 0

那么你已经有了这些，只要确保法线是单元化的。

如果以解析形式给出:Sum(i = 1 to n: a[i] x[i]) + d = 0，则向量 A = (a 1 , ... a[n] ) 是平面的法线， N = A/||A||是单位平面正常。平面上的点 O(原点)为 d N。

您可以通过将每个点 P 投影到 N 添加检查参数的符号来测试每个点 P 在哪一侧:

令 V = P - O。V 是从所选原点 O 到 P 的向量。

令 s N 为 projection of V onto N .如果 s 为负，则 P 在超平面“下方”。

如果您对这个主题不熟悉，您应该转到有关矢量投影的链接，但我将在此处使用我的符号进行总结。或者，您可以相信我的话，直接跳到最后的公式。

如果 alpha 是 V 和 N 之间的夹角，那么根据余弦的定义我们有 cos(alpha) = s||N||/||V|| = s/||V||因为 N 是单位正常。但我们也从矢量代数中知道 cos(alpha) = ||V||(V.N)，其中“.”是标量积(又名点积，或欧氏内积)。

将这两个表达式等同于 cos(alpha) 我们有

s = (V.V)(V.N)

(利用 ||V||^2 == V.V 这一事实)。

所以你的处理工作是计算 N 和 O，你的测试是:

bool is_under = (dot(V, V)*dot(V, N) < 0.);

我不相信它可以做得更快。