给定一个大立方体（轴对齐并在整数坐标上）和许多较小的立方体（也轴对齐并在整数坐标上）。我们如何检查大立方体是否完全被较小的立方体填充。
目前我们检查：
这对于少量多维数据集是可以的，但我们需要支持对尺寸大于 2^32 的多维数据集的这种测试。即使在 2^16 处，填充大立方体所需的小立方体数量也足够大，以至于第 2 步需要一段时间（O(n^2) 检查每个立方体与其他立方体不相交）。
有更好的算法吗？
编辑：
对此似乎有些困惑。我不是想把一个立方体分成更小的立方体。那已经完成了。我们程序的一部分将大型 OpenCL 范围（整数坐标上的轴对齐立方体）拆分为许多适合硬件作业的较小范围。
我正在做的是连接到这个系统并检查它产生的作业是否正确覆盖了大的初始范围。我上面的算法有效，但它很慢，并且考虑到我们必须运行的测试数量，我想尽可能快地保持这些测试。
我们在谈论 3D 对吗？
对于 2D，可以执行类似（但更简单）的过程（我相信，使用 O(n log n) 运行时间算法）。
下面的基本思想是扫线算法。
请注意，矩形相交可以通过检查任何立方体的任何角是否包含在任何其他立方体中来完成。
您可以对 (2) 进行如下改进：
将每个立方体在 yz 平面上拆分为 2 个矩形（因此您将有 2 个由同一组 4 个 (y,z) 坐标定义的矩形，但矩形之间的 x 坐标会有所不同）。
将 x 坐标较小的矩形定义为立方体的开始，将另一个矩形定义为立方体的结束。
按 x 坐标对矩形进行排序
有一个最初为空的区间树
（每个区间还应存储对其所属矩形的引用）
对于每个矩形：
在区间树中查找矩形每个点的 y 坐标。
对于每个匹配区间，查找它的矩形并检查该点是否也包含在 z 坐标内（这就是所需要的，因为树只包含正确范围内的 x 坐标，我们通过执行以下操作检查 y 坐标区间查找）。
如果是，我们就有重叠。
如果矩形是立方体的起点，则将矩形的 2 个 y 坐标作为区间插入到区间树中。
运行时间介于 O(n)（最佳情况）和 O(n 2 )（最坏情况）之间，具体取决于 x 和 y 坐标中有多少重叠（重叠越多越差）。
另一个去，再次只解决原始问题中的第 2 步：
2^18. 这些坐标定义了沿空间填充曲线的间隔，因此对它们进行排序并寻找重叠。时间复杂度可能以排序为主，空间复杂度可能相当大。