如何将构成凸包的半空间转换为一组极点？

Question

我有一个凸集，位于欧几里得空间中（3D，但希望为nD提供答案），由一组半空间（法向量+点）描述。

除了计算所有由3个（或n个）半空间相交得到的点并排除非极点之外，是否有更好的算法来寻找凸集的极点？

- Gyro Gearloose

---

我可以翻译这篇文章的摘要，但无法访问该链接。请提供需要翻译的内容或将文本直接复制到此处。 - Paul Hankin

con2vert Matlab脚本使用原始对偶多面体方法实现了这一点；该脚本并不是很长。 - user3717023

@Normal 谢谢，从描述来看，这正是我所需要的。然而，当我点击“关注此文件”时，系统要求我进行注册。我不想轻易地留下我的个人信息。这是专利或许可思维，还是免费的？ - Gyro Gearloose

“Watch this file” 意味着会收到新版本的通知。下载按钮在右侧。然而，此文件没有许可证。我发现这个文件已经“启发”了一个后来的提交，它是 BSD 许可证的，并且似乎取代了前者的功能。 - user3717023

@Normal，谢谢，看起来我对那些试图向每个人收费的小丑有点过于多疑了。如果您能提供一些帮助（链接）以了解如何阅读此内容（特别是“c=A\b”），我将接受此作为答案。 - Gyro Gearloose

Answer 1

关键术语是多面体P的顶点枚举。下面描述的算法的思想是考虑dual多面体P*。P的顶点对应于P*的面。使用Qhull有效地计算P*的面，然后通过解相应的线性方程子系统找到顶点。

该算法是在受BSD许可的Matlab工具集Analyze N-dimensional Polyhedra in terms of Vertices or (In)Equalities中实现的，由Matt J编写，特别是其组件lcon2vert。然而，为了阅读算法并在另一种语言中重新实现它，使用Michael Kleder的旧版和简单的con2vert文件更容易，这是Matt J项目所依赖的。

我将逐步解释它的作用。各个Matlab命令（例如convhulln）在MathWorks网站上有文档，并引用底层算法。

---

输入由形如Ax<=b的线性不等式集合组成，其中A是一个矩阵，b是一个列向量。

第一步。尝试找到多面体内部的一个点。

首先尝试c = A\b，它是超定线性系统Ax=b的最小二乘解。如果分量上满足A*c<b，则这是一个内部点。否则，尝试多变量最小化，目标函数为0和所有数字A*c-b的最大值。如果无法找到一个满足A*c-b<0的点，则程序退出并显示“无法找到内部点”。

第二步。将多面体平移，使原点成为其内部点。

在Matlab中通过b = b - A*c实现。由于0现在是一个内部点，b的所有条目都是正数。

第三步。归一化，使右手边为1。

这只是Matlab中的一个命令：D = A ./ repmat(b,[1 size(A,2)]);，对A的第i行进行了b(i)的除法。从此以后，只使用矩阵D。请注意，D的行是在开头提到的双面体P*的顶点。

步骤4. 检查多面体P是否有界

如果多面体P的对偶面P*的顶点位于原点通过某些超平面的同一侧，则多面体P是无界的。可以使用内置函数convhulln来检测这个问题，它计算给定点的凸包体积。作者检查将零行附加到矩阵D是否增加了凸包的体积；如果增加了，程序将退出并显示“检测到非边界约束”。

步骤5. 计算顶点

这是循环部分。

for ix = 1:size(k,1)
    F = D(k(ix,:),:);
    G(ix,:)=F\ones(size(F,1),1);
end

在这里，矩阵k编码P*的面，每行列出面的顶点。矩阵F是D的子矩阵，包含P*的一个面的顶点。反斜杠调用线性求解器，并找到P的一个顶点。

步骤6：清理

由于在步骤2中对多面体进行了平移，因此使用V = G + repmat(c',[size(G,1),1]);来撤消此平移。其余两行尝试消除重复的顶点（不总是成功）。

- user3717023

Answer 2

我是polco的作者，这是一款实现“双重描述法”的工具。双重描述法已被证明在许多退化问题上表现良好。它已被用于计算数千万个发生器，主要用于计算系统生物学问题。

该工具使用Java编写，在多核CPU上并行运行，并支持各种输入和输出格式，包括文本和Matlab文件。您可以通过提供的链接到苏黎世联邦理工大学的一个部门了解更多关于该软件和双重描述方法的信息和出版物。

- marco