凸多边形

如果一个平面 多边形 包含连接其任意两点的所有线段，则它是凸多边形。例如，正五边形是凸多边形（左图），而凹五边形则不是（右图）。不是凸多边形的平面多边形被称为凹多边形。

设一个简单多边形有 个顶点 ，其中 , 2, ..., ，并将边向量定义为

(1)

其中 被理解为等同于 。那么，多边形是凸多边形当且仅当从一个边向量到下一个边向量的所有转向都具有相同的方向。因此，一个简单多边形是凸多边形当且仅当

(2)

对于所有 ，具有相同的符号，其中 表示垂直点积 (Hill 1994)。然而，已知一种更有效的测试，它不需要预先知道多边形是简单的 (Moret and Shapiro 1991)。

快乐结局问题考虑凸 边形和最小点数 （在一般位置），在这些点中总是可以找到一个凸 边形。n=3、4、5 和 6 的答案分别是 3、5、9 和 17。据推测 ，但仅证明了

(3)

其中 是二项式系数。