在非负半轴上，寻找一个由轴对齐的超立方体组成的集合的顶点的算法，其中所有超立方体的一个顶点都在原点。

Question

假设我有一个在D维空间中的N个轴对齐超立方体的集合。

每个超立方体都有一个定点在原点，一个顶点在正半轴（即所有坐标严格为正）。后者定义了超立方体，因此超立方体的集合可以由一个顶点集合来给出，每个超立方体对应一个顶点。

您可以假设我已经从超立方体列表中删除了任何一个超立方体，该超立方体严格包含于另一个超立方体内。（当前我是通过一个简单的O（N ^ 2 * D）算法来实现的。附带问题：我能做得更好吗？）

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

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

在D维中有多少这样的顶点？（两个超立方体的情况下，似乎只会产生一个新的顶点，因此可能仍然是N-1？）如何高效地找到这些顶点？

- cfp

---

“我需要找到并集的顶点” - 这句话不是很清楚。您想要在某个数据结构中表示并集的形状吗？如果是这样，请问使用哪一种数据结构？ - HEKTO

对于数据结构：列表就可以了。 关于我的猜想的反例：是的，你是对的。对于那些像我一样难以想象3D的人，可以使用例如来自这里http://jialunliu.com/how-to-use-matlab-to-plot-3d-cubes/的MATLAB cube_plot函数，代码如下： cube_plot([0,0,0],3,2,1,[1,0,0]); hold on; cube_plot([0,0,0],2,1,3,[0,1,0]); cube_plot([0,0,0],1,3,2,[0,0,1]); hold off; 结果是https://ibb.co/j89pg0M，有4个新顶点（不包括坐标为0的顶点）。 - cfp

新顶点列表？你打算用它做什么？通常最好设计一个数据结构，以及一组对其进行操作的方法。你当前的表示形式是一组相交的超立方体，也是一种数据结构，但可能不支持你需要的所有操作 - 这就是为什么你想将其转换为其他形式的原因，对吧？ - HEKTO

他们在线性规划问题中输入约束条件。所以一个列表就足够了。 - cfp

在这种情况下，您需要构建所有超盒子的交集，而不是联合。 - HEKTO

Answer 1

一些缩写： Hj 代表“超立方体 j”，具有一个顶点位于原点，另一个顶点位于 {xi，yi，zi，wi等}。

如果 Hi 包含在 Hj 中，则 xi <= xj，yi <= yj，zi <= zj，依此类推。

如果您有D 个已排序的坐标列表，每个维度一个，则可以通过查询坐标索引来轻松检查 Hi 是否为内部 Hj ：posXi < posXj 和 posYi < posYj 和 posZi < posZj，等等。请注意，“and”而不是“or”条件。

如果某些Hi不遵守所有Hj的“and”规则，则顶点i是一个新顶点。
如果某个坐标T是“out”：posTi > posTlast，则顶点i是一个新顶点。

- Ripi2

---

我不确定我理解这是如何生成新顶点列表的。你能展示一下它如何应用于HEKTO上面给出的例子(3,2,1)，(2,1,3)和(1,3,2)吗？ - cfp