凸多面体的每个顶点都能找到吗？

让我来回答一下吧。 我之前也思考过类似的问题。 首先，假设提问者确实需要计算顶点的坐标，而不是使用平面方程表示，他可以使用其他方法（例如答案中提到的方法）。

先说结论吧。 这个问题的一般情况就是计算几何中的半空间相交问题（half-space）。 在非简并情况下（即，当这些半空间的交集不为空时），使用射影极对偶性（极性）。 ），相当于凸包（hull）问题。 如果输入大小为n，那么在维度d=2,3的情况下，当前的确定性算法复杂度为O(n\log h)，其中h是输出的大小。 在高维情况（d\）下，确定性算法当前最坏情况复杂度为 O(n\log n+n^{\d/2\})。

首先，提问者说它是凸多面体。 可能有人会想，既然已经给出了这些半平面可以组成凸多面体的条件，那我们是不是可以利用呢？ 我的答案不确定，这取决于你的输入是什么样的。 如果你的输入已经给出了多面体（ ）的组合描述，它决定了这些平面之间的关系，比如与这些平面相邻的平面，那么就不需要忘记它超时空大帝国顶点，直接建立方程组即可。 但是，如果给定的输入只是一个无序平面方程，即给定多面体的面描述（facet），那么据我所知，目前还没有有效的算法可以直接计算多面体而不需要计算组合描述。 ( ) 的顶点描述。 因此，我们需要计算组合描述。

我们换个话题，解释一下为什么直接联立方程不可行。 在 d 维空间中，需要 d 个方程来确定一个点。 那么总共可以找到 {n \ d}=O(n^d) 个点，但并不是所有这些点都有用。 你必须在多面体中放入一些。 放弃外点显然是一个麻烦的问题。 就算你知道怎么解，你的算法首先也会有O(n^d)的大头。 无论你怎么做，都没有比这更有效率的了。

现在我们假设输入是一系列平面方程，或更准确地说，是半空间不等式。 那么在非退化的情况下，我们可以找到一个被所有半空间包含的内点（可以通过求解线性规划来求解），将坐标原点变换到该点，然后将所有半空间（或超平面， ）到点，然后求解该点的凸包问题。 凸包的每个面对应于原始问题的一个顶点。 问题解决了。

凸包问题非常重要，因为有很多相关问题都可以转化为凸包问题，比如这里的半空间相交问题。 其他比较重要的还有三角测量和图表，这些都是非常实际的问题。 至于凸包算法，不止一种。 确定性算法主要可以分为三类，增量方法、图遍历方法和分而治之方法。 分治法通常仅适用于小尺寸。 增量法主要是在得到的结果上逐一相加。 图的遍历对应于单纯形法中顶点的移动。 每一步根据当前状态选择下一个多边形面。 它也被称为礼品包装。 -）算法。

凸包算法的复杂性主要在于组合问题。 对于不同的点集，最终凸包描述的大小有很大不同。 很多时候，最坏的复杂度往往并不能代表实际的效果。比如使用一些启发式的方法（参见

库尔

，里面的qhalf可以计算半空间交集），在低维度（2~8左右）实际效果还不错。 在高维情况下，我们仍然不知道更好的凸包算法能做什么。 获奖者姚期智曾证明，对于目前已知的算法类型，凸包算法的下界为O(n\log n)。 然而，我们不知道是否还有其他类型的方法可以比当前最坏情况上限 O(n\log n+n^{\d/2\}) 做得更好。