检查小立方体是否填充更大的立方体。

Question

给定一个大立方体(轴对齐和整数坐标)，以及许多较小的立方体(也是轴对齐和整数坐标)。我们如何检查大立方体是否被较小的立方体完美填充。

目前，我们检查：

1. 对于每个小立方体，它都完全包含在大立方体中。
2. 它不与任何其他小立方体相交。
3. 小立方体的体积之和等于大立方体的体积。

对于少量的多维数据集来说，这是可以的，但是我们需要支持尺寸大于2^32的多维数据集的测试。即使在2^16，填充大立方体所需的小立方体数量也足够大，因此步骤2需要一段时间(O(n^2)检查每个多维数据集不与其他多维数据集相交)。

有更好的算法吗？

编辑：

这件事似乎有些混乱。我不是想把一个立方体分割成更小的立方体。已经做好了。我们程序的一部分将大的OpenCL范围(整数坐标上的轴对齐立方体)分割成许多适合于硬件作业的较小范围。

我所做的是连接到这个系统，并检查它产生的作业是否正确地涵盖了大范围的初始范围。我上面的算法是有效的，但是它很慢，并且考虑到我们必须运行的测试数量，我希望尽可能快地保持这些测试。

Answer 1

• 排序您的插入立方体
• 将最大的插入多维数据集插入到多维数据集的一个角落中，并将剩余的多维数据集拆分为子多维数据集。
• 在第一个适合的子多维数据集中插入第二个最大的插入多维数据集，并将该子多维数据集的其余子多维数据集添加到子多维数据集中。
• 等。

Answer 2

再来一次，同样只讨论原来问题中的第二步：

1. 定义具有良好空间局部性的空间填充曲线，如三维Hilbert曲线.
2. 对于每个立方体，计算曲线上的坐标对，曲线在这些点上既可以进入也可以离开立方体。空间填充曲线将进入和离开一些立方体不止一次，为这些情况计算多对坐标。
3. 现在我不知道有多少对坐标，但我猜只有2^18。这些坐标定义了沿空间填充曲线的间隔，因此对它们进行排序并查找重叠。

时间复杂性可能是由这类主导的，空间复杂性可能相当大。