凸多边形
tū duō biān xíng
凸多边形的所有内角都小于 180 度，每条对角线都完全位于图形内部。
Definition
凸多边形没有"凹陷"或向内的角，每个角都指向外部，所有内角都小于 $180^\circ$；等价地说，连接内部任意两点的每条线段(以及每条对角线)都完全位于多边形内部。所有正多边形都是凸的，外角和恰好为 $360^\circ$，严格来说，多边形 $P$ 是凸的，当且仅当它是若干半平面的交集；它的顶点恰好是其凸包的极值点。
Example
正方形、三角形、正六边形和停车让行标志都是凸的；箭头或星形有凹陷，不是凸的，它们总是看起来向外"鼓出"某处、向内凹陷某处。正五边形是凸的，因为所有内角都是 $108^\circ<180^\circ$；有一个大于 $180^\circ$ 内角(优角)的箭头形状是凹的。给定点 $(0,0), (1,0), (0,1), (0.5,0.5)$，凸包是三角形 $(0,0), (1,0), (0,1)$，因为 $(0.5,0.5)$ 位于内部，可以用格拉哈姆扫描法或贾维斯步进法等算法在 $O(n\log n)$ 时间内求出。
Key Insight
一个简单的判别法：如果一根拉紧的橡皮筋环绕图形时接触到每一个顶点，它就是凸的；如果橡皮筋因某个顶点被向内推而"跳过"了它，这个多边形就是凹的。凸多边形拥有许多凹多边形所没有的性质：所有对角线都留在内部，三角剖分很容易，重心总是在内部，而凸性正是线性规划基本定理(单纯形法)背后的关键假设，其中在凸多边形上取最小值的函数总是在某个顶点处取得最小值，这一原理可以推广到更高维度的凸多胞形。