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

Question

我有一个凸集在欧几里得空间(3D，但想回答nD)，它的特征是有限的半空间集(法向量+点)。

是否有更好的算法来寻找凸集的端点，而不是计算蛮力，所有的点都是3(或，n)半空间的交点，并消除了那些不是端点的点？

Answer 1

关键术语是一个多边形P的顶点枚举，下面描述的算法的思想是考虑对偶多边形P*。然后，P的顶点对应于P*的面。利用Qhull对P*的各方面进行了有效的计算，然后通过求解相应的线性方程组来寻找顶点。

该算法是在由用顶点或( in )等式分析N维多面体 ( 马特J )编写的BSD授权工具集Matlab中实现的，特别是其组件lcon2vert.然而，为了读取该算法并重新实现它的另一种语言，使用Michael的旧的、更简单的con2vert文件就更容易了，Matt的项目就是以这个文件为基础的。

我会一步一步地解释它的作用。单独的Matlab命令(例如，塞赫耳恩)记录在MathWorks站点上，并引用底层算法。

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

步骤1.尝试定位多边形的内部点

首先尝试的是c = A\b，它是超定线性系统Ax=b的最小二乘解.如果A*c<b在组件上保持不变，这就是内部点。否则，尝试多变量最小化，目标函数为0的最大值，所有数为A*c-b。如果找不到A*c-b<0保存的点，程序就会以“找不到内部点”退出。

步骤2.翻译多面体，以便原点是它的内点

这是由b = b - A*c在Matlab中完成的。由于0现在是内部点，所以b的所有条目都是正的。

步骤3.规范化，使右侧为1

这只是A的第一行除以b(i)，由D = A ./ repmat(b,[1 size(A,2)]);在Matlab中完成。从现在开始，只使用矩阵D。请注意，D的行是开头提到的对偶多点P*的顶点。

步骤4.检查多边形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是由P*的一个面的顶点组成的D的子矩阵。反斜杠调用线性求解器，并找到P的一个顶点。

步骤6:清理

由于在第二步翻译了多个表位，所以这个翻译是用V = G + repmat(c',[size(G,1),1]);撤销的。其余两行试图消除重复的顶点(并不总是成功的)。

Answer 2

我是波尔科的作者，这是一个实现“双重描述方法”的工具。双描述方法对于许多退化问题都是行之有效的。它已经被用于计算数千万台发电机，主要用于计算系统、生物问题。

该工具是用Java编写的，在多核CPU上并行运行，支持各种输入和输出格式，包括文本文件和Matlab文件。您将找到更多的信息和出版物有关的软件和双重描述方法，通过给定的链接到ETH苏黎世大学系。