闵可夫斯基和入门

极坐标系

对于直角坐标系的点 $(x,y)$ ，它可以用极坐标系 $(r,\theta)$ 表示，其中

$r=\sqrt{x^2+y^2}\\ \theta = \text{atan2}(y,x)$

atan2 是已将象限纳入考量的反正切函数，或者

$\theta = \begin{cases} \arctan(\frac{y}{x}) & x>0\\ \arctan(\frac{y}{x})+\pi & x<0 \operatorname{and} y\ge 0\\ \arctan(\frac{y}{x})-\pi & x<0 \operatorname{and} y<0 \\ \frac{\pi}{2} & x=0 \operatorname{and} y>0 \\ -\frac{\pi}{2} & x=0 \operatorname{and}y<0 \\ 0 & x=0 \operatorname{and} y=0 \end{cases}$

也就是向量 $(x,y)$ 与 $x$ 轴正半轴的夹角。atan2 的值域为 $(-\pi,\pi]$ 。

$\theta$ 是所谓的极角。按极角排序也就是按 $\theta$ 排序。

半平面交、凸包和凸多边形

三者其实没有太大区别。只是半平面交是用直线方程表示，而凸包是用顶点集表示，多边形则是由边的向量表示。

半平面交和凸包的对偶并不是单纯的表示方式的变化，这一点要注意。除非你用半平面交的交点集表示它，这才是单纯的表示方式的变化。

像闵可夫斯基和之类的，三者其实都可以经过简单的转化后使用。

半平面交对偶凸包

考虑 $n$ 条直线 $y=k_ix+b_i$ ，我们要求 $y\le k_ix+b_i$ 形成的半平面交。

显然这是上凸的半平面交。

首先将直线按斜率从大到小排序。然后依次加入直线。假设当前末尾的直线和倒数第二的直线分别是 $f',f''$ 。

则新加入一条 $y=kx+b$ 则要一直删除末尾直线，直到

$-\frac{b'-b''}{k'-k''} < -\frac{b-b''}{k-k''}$

也就是交点的横坐标关系。

不妨设 $p=(k,b),p'=(k',b'),p''=(k'',b'')$ ，那么上述算法就转化为，将点按照横坐标从大到小排序，算法过程中删除末尾点，直到

$\frac{b'-b''}{k'-k''} > \frac{b-b''}{k-k''}$

稍作化简：

$(k-k'')(b'-b'') > (k'-k'')(b-b'')\\ \det(p-p'',p'-p'')>0$

如果我们把从大到小排序改为从小到大排序，那么该式就变成了 $\det(p-p'',p'-p'')<0$ ，也就是下凸壳。

因此上凸的半平面交对偶后为下凸壳。

同理可得，下凸的半平面交对偶后为上凸壳。

不过要注意的是，这对偶关系只是考虑了半平面交上的点的情况。对于半平面交里和外的点则没有对偶（也可能是我没有分析出来的原因）。换言之这个对偶只描述了半平面交的形态。