Low-Dimensional Linear Program
- 问题形式
- 其中的\(d\)特别的小，但c\(n\)可以很大
- 几何上的理解
- 相关方法对比
- the simplex algorithm
- 能得到精确解，但最坏复杂度是指数时间的
- GLPK用的是simplex方法解LP
- IPM
- 复杂度是多项式时间，但不能得到精确解
- Seidel’s Algorithm
- 在低维、高约束量的前提下，具备线性时间复杂度，精确解的优势
- the simplex algorithm
- Seidel’s Algorithm流程
- random order可以通过Fisher-Yates方法生成
- 高斯消元本质是将\(dim\)降维成\(dim-1\)。
- 高斯消元的时候，每次选择系数的绝对值最大的元去消，可以保证算法的数值稳定性。从几何上理解，对于平面\(ax+by+cz=d\)来说，如果\(z\)的系数的绝对值最大，说明平面和z轴最垂直（和xy平面最平行），将z消去后，信息损失很少。
- Seidel’s Algorithm应用
- Linear Separability(点集碰撞检测)
- 本质上是找一个超平面，使得绿色点集中的所有点在超平面的一侧，红色点集中的所有点在超平面另一侧
- Chebyshev Center(切比雪夫中心)
- 本质上是找一组超平面的最大内切圆，圆心即距离所有边都最远的点
- 假设这组超平面为\(Ax\leq b\)，其中\(A=\left [a_{1}^{T},a_{2}^{T},…,a_{m}^{T}\right]^{T}\)，\(b=\left [b_{1},b_{2},…,b_{m}\right]^{T}\)，假设\(\left|a_{i}^{T}\right|=1\)，那这里的\(a_{i}^{T}\)就是第\(i\)个超平面的单位法向量
- 由于球在超平面内部，所以球上的每个点都满足\(Ax\leq b\);为了让点距离每个超平面都最远，我们引入一个margin\(y\)，我们在保证\(Ax+y\leq b\)的同时，让\(y\)尽可能大
- 写成向量形式就是\(min_{\bar{x}\in R^{n+1}}-\bar{x}^{T}e_{n+1},s.t.(A,1)\bar{x}\leq b\)，其中\(\bar{x}=(x^{T},y)^{T}\)，\(e_{n+1}=(0,…,0,1)^{T}\)
- 利用切比雪夫中心进行凸包碰撞检测
- 已知一个凸包为\(A_{1}x\leq b_{1}\)，另一个凸包为\(A_{2}x\leq b_{2}\)，联立组成新的凸包，\(\begin{bmatrix}A_{1}\\A_{2}\end{bmatrix}x\leq \begin{bmatrix}b_{1}\\b_{2}\end{bmatrix}\)并求新凸包的切比雪夫中心，如果有解，则说明两个原凸包有交集
- Linear Separability(点集碰撞检测)
