求非负正交轴向超长方体并集顶点的算法

Question

假设我有一个N轴对齐的D维超长方体的集合。

每个超长方体在原点都有一个顶点，并且在正投影中有一个顶点(即所有坐标都是严格正的)。后一个顶点定义了超立方体，因此超立方体的集合可以由一个顶点集合给定，每个超立方体一个顶点。

你可以假设我已经从超长方体的列表中删除了严格包含在另一个超长方体中的任何超长方体。(目前我是通过一个朴素的O(N^2*D)算法来做这件事的。附带问题:我能做得更好吗？)

我需要找到所有超长方体并集的顶点，不包括任何具有一个或多个零坐标的顶点。

在二维中，有N-1个这样的顶点，并且可以通过在一个(任意)坐标上对顶点进行排序来有效地找到它们，即在O(N log(N))中。

在D维中有多少这样的顶点？(对于两个立方体，似乎只有一个新顶点，所以可能仍然是N-1?)如何有效地找到这些顶点？

Answer 1

一些缩写：Hj的意思是"Hipercuboid j"，在原点有一个顶点，在{xi, yi, zi, wi, etc}有相反的顶点。

如果Hi包含在Hj中，那么xi<=xj、yi<=yj、zi<=zj等等。

如果你有D排序的坐标列表，每个维度一个，那么很容易通过简单的坐标索引查询来检查Hi是否是Hj的内部：posXi<posXj和posYi<posYj以及posZi<posZj等。注意“”，而不是"or"，条件。

如果某个顶点没有遵守所有顶点的"and“规则，那么这个Hi i就是一个新顶点。

如果某个坐标T为"out"：posTi > posTlast，则顶点i为新顶点。