求立方体中三维点子集的算法复杂性

Question

给定一个三维整数数组，确定这些整数中哪一个存在于立方体中的算法复杂度是多少？我假设这些点可以在多个并发数据结构中表示，每个数据结构在一个或多个维度中排序。

我的直觉告诉我，在1D中给出了一个排序的点数组，它可以确定O(log(n) )之类的一些下界和上界之间的点子集，但我非常感谢其他人对这个概念提供的任何见解(以及其他人可以为多维情况提供的任何帮助！)。

Answer 1

如果你不熟悉所涉及的数学，我建议你先用一个矩形在二维上做这个问题。这样的话，你就可以熟悉数学了，这实际上只是一些基本的三角学。在那之后，提升到三维并不是很困难。

如果立方体(或矩形)是对轴的，那么这个问题就简单得多，所以您可能应该先这样做。有关确定所需旋转的示例，请参见How to calculate rotation angle from rectangle points?。

一旦确定了旋转角度，就可以将矩形转换为原点，并通过在这里接受的答案：Drawing a Rotated Rectangle中执行前两个步骤来旋转它。

你现在有一个轴对齐的矩形，在原点的中心。

最后，针对您的每一点：

1. 应用与应用于矩形的相同的平移和旋转。
2. 测试结果点中的x和y坐标是否在矩形内。这最多是四次边界检查的问题。
3. 如果点在矩形中，保存它。

一旦在两个维度中完成了这些操作，就应该能够将这些概念应用到三维中。

算法为O(n)，其中n为点数。