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

Question

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

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

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

score 2 · Accepted Answer

如果您愿意对这些点进行预处理，那么您必须至少访问每个点一次，即 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 是V 到 N 的投影。如果 s 为负数，则 P 在超平面“下方”。

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

如果 alpha 是 V 和 N 之间的角度，那么根据余弦的定义，我们有 cos(alpha) = s||N||/||V|| = s/||V|| 因为 N 是单位法线。但是我们也从向量代数中知道 cos(alpha) = ||V||(VN)，其中 "." 是标量积（又名点积，或欧几里得内积）。

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

s = (VV)(VN)

（使用 ||V||^2 == VV 的事实）。

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

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

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

score 0 · Accepted Answer

0

设置点值时，请使用该点设置的检查条件。然后增加或不增加计数器。上）

于 2012-08-12T16:17:43.323 回答

score 0 · Accepted Answer

我通过使用分治法和二进制搜索与 O(N log N) 预处理时间复杂度和 O(N log N) 内存复杂度在 2D 维度中找到了 O(logN) 算法

基本思想是点可以分为左N/2点和右N/2点，线下的点数（2D维度）是线下的左点数与线下点数之和线下的正确点。我将把整个点分成“左”和“右”的无限线称为“分界线”。分割线看起来像'x = k'

如果每个'left points'和'right points'按y轴顺序排序，则可以通过二分查找'y值的点的数量'快速找到特定点的数量-右下角的点低于直线与分界线交点的y值。

因此时间复杂度为

T(N) = 2T(N/2) + O(log N)

最后时间复杂度为 O(log N)

3 回答 3