用于查找非负正数中轴对齐超长方体并集的顶点的算法，所有顶点都位于原点处-解网

问：

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

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

你可能会认为我已经从超长方体列表中删除了严格包含在另一个超长方体中的任何超长方体。（目前我正在通过一个朴素的 O（N^2*D）算法来做到这一点。附带问题：我能做得更好吗？

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

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

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

算法语言不可知复杂性理论计算几何

对于数据结构：列表就可以了。关于我的猜想的反例：是的，你是对的。对于那些觉得 3D 难以可视化的人（像我一样），您可以使用例如 MATLAB cube_plot 函数，从这里 jialunliu.com/how-to-use-matlab-to-plot-3d-cubes 代码：cube_plot（[0,0,0]，3,2,1，[1,0,0]）;坚持;cube_plot（[0,0,0]，2,1,3，[0,1,0]）;cube_plot（[0,0,0]，1,3,2，[0,0,1]）;拖延;结果是 ibb.co/j89pg0M 了 4 个新顶点（不包括坐标为 0 的顶点）。

0赞 HEKTO 5/11/2019

新顶点列表？你打算用它做什么？通常，将数据结构与一组操作一起设计是有意义的。您当前表示为一组相交的超框也是一种数据结构，但它可能不支持您需要的所有操作 - 这就是您想要将其转换为其他东西的原因，对吧？

0赞 cfp 5/11/2019

它们进入线性规划问题的约束。所以一个列表真的就足够了。

答：

0赞 Ripi2 5/11/2019 #1

Some abreviature：表示“Hipercuboid j”，在原点处有一个顶点，在处有相反的顶点。Hj{xi, yi, zi, wi, etc}

如果包含在其中，则、、、等。HiHjxi<=xjyi<=yjzi<=zj

如果你有 D 个排序的坐标列表，每个维度一个，那么很容易通过对坐标索引的简单查询来检查是否在内部：和和等。请注意“and”，而不是“or”条件。HiHjposXi<posXjposYi<posYjposZi<posZj

如果有些顶点不遵守所有顶点的“和”规则，那么顶点就是一个新的顶点。
如果某个坐标是“out”：则该顶点是新顶点。HiHjiTposTi > posTlasti

用于查找非负正数中轴对齐超长方体并集的顶点的算法，所有顶点都位于原点处

Algorithm for finding the vertices of a union of axis-aligned hypercuboids in the nonnegative orthant, all with one vertex at the origin

评论

评论