经典证明：不断把凹的部分翻出来，总能把凹多边形变凸吗？

左图是一个凹多边形，而且凹得相当厉害。作为一个完美主义者，我很难容忍这么一个图形，总想着要把凹进去的部分翻出来，把它还原为一个凸多边形。不幸的是，翻折之后的结果仍然不是凸多边形，图中又产生了新的凹陷。于是，我们想继续把凹进去的部分往外翻，直到整个图形变成凸多边形为止。问题是，这个过程有完吗？换句话说，我们一定能通过有限多步翻折，把凹多边形变成凸的吗？

这个问题有着非常纠结复杂的历史。这个问题最早可能是由数学家 Paul Erdős 正式提出的。 1935 年，他在 American Mathematical Monthly 上猜想，经过有限步翻折之后，凹多边形一定能变凸。 1939 年， Béla Szőkefalvi-Nagy 给出了一个证明。因此，这个结论又叫做 Erdős-Nagy 定理。有趣的是，这个问题是如此的自然，以至于在此之后，又有一大堆人重新提出并研究了这个问题，而且他们明显并不知道相互之间的已有研究。这事儿给我们带来的好处就是，我们有了 Erdős-Nagy 定理的好几种截然不同的证明方法。不过，这些证明或者太长，或者太高深，或者又有些漏洞。 1999 年， Godfried Toussaint 从这些证明中取长补短，给出了一个比较初等的证明。

在下面的讨论中，我们可能会遇到上图所示的情况：某次翻折之后，三个相邻顶点正好共线，构成了一整条长边。那么，今后中间的那个点将永远位于这条边上，因此我们可以放心地把它从顶点集里去掉。于是，我们可以默认，下面讨论的所有多边形，边上都不会有“废”的顶点。

让我们先来看一个引理：任意给定一个凸多边形后，我们总能找到一个 ε ，使得只要该凸多边形的每一个顶点都移动了不超过 ε 的距离，得到的新多边形仍然是凸的。

让我们考虑凸多边形上的某个顶点 V_i，以及它的两个相邻顶点 V_i-1和 V_i+1。把 V_i-1V_i的中点和 V_iV_i+1的中点的连线记为 l 。于是， V_i、 V_i-1、 V_i+1这三个顶点到 l 的距离都是相等的。让我们把这个距离值为 r 。现在，以 r 为半径，分别以这三个顶点为圆心作圆，那么，只要每个顶点都在各自的圆内移动，这些顶点与直线 l 的相对位置都保持不变， V_i-1和 V_i+1仍然在 l 的同侧， V_i仍然在 l 的另一侧。也就是说，整个多边形在 V_i这个点仍然是凸的。注意到，对于每个不同的顶点 V_i，我们都能找到这么一个合适的 r 。取所有这些 r 当中的最小值，它就是一个满足要求的 ε 。

下面我们开始证明，对于任意的一个凹多边形，经过有限次的翻折后，最后总能变成一个凸多边形。

首先，让我们考虑初始时多边形内的任意一点 X ，以及多边形上的任意一个顶点 Y 。今后，这个 Y 点的位置将不时发生变化。我们把第 i 次翻折之后 Y 点的位置记作 Y⁽ⁱ⁾。注意到，由于每次翻折之后，新的凸多边形都完全覆盖了原来的凸多边形，因此 X 将永远留在凸多边形的内部。现在我们来考虑每一次翻折对 X 和 Y 之间的距离将带来怎样的影响，在第 i 次翻折之前， X 和 Y^(i-1)都在翻折的折痕同侧，在第 i 次翻折之后， Y 点要么根本没动，要么被对称地翻折到了折痕的另一侧。在前一种情况下， X 到 Y 的距离并没有变；在后一种情况下，假设 X 和 Y⁽ⁱ⁾的连线与折痕交于点 K ，则 XY⁽ⁱ⁾= XK + KY⁽ⁱ⁾= XK + KY^(i-1)> XY^(i-1)，可见 X 到 Y 的距离严格地增加了。

但是，多边形的翻折操作不会改变整个多边形的周长，因此 X 到 Y 的距离有一个上限：它最多等于整个多边形周长的一半（类似于上图的极端情况）。这表明， XY⁽¹⁾, XY⁽²⁾, XY⁽³⁾… 的长度构成了一个有上界的不下降序列，因而这个序列有一个极限。也就是说，最终 Y 点到 X 点的距离会慢慢固定下来。注意到，由于 X 的任意性，因而我们实际上说明了，随着翻折次数的增加， Y 点到初始多边形内的任意一点的距离都会固定下来，因此事实上， Y 点存在一个极限位置。根据同样的道理，多边形的所有顶点都将慢慢趋近于它们各自的极限位置，因此整个多边形也就存在一个极限。显然，这个极限多边形一定是凸的，否则它还能再翻折，与它是一个极限相矛盾。

别忘了我们之前的引理：我们总能够找到一个 ε ，使得极限多边形的每个顶点都移动不超过 ε 的距离之后仍然能保持凸性。现在，在极限多边形的每个顶点周围都画上一个半径为 ε 的圆盘。对于初始多边形的每一个顶点，它最终都会收敛到它的极限位置，因而在有限步翻折之后，它必然会踏入它所对应的圆盘。因此，我们只需要等待有限步翻折，所有的点都会踏入各自的圆盘。此时，我们便得到了一个凸多边形。

这个证明很有意思：结论本身是离散的，证明却用到了连续和极限的思想。由此带来的结果是，我们虽然证明了凹多边形能在有限步之内变凸，但却完全无法给出所需步骤数的一个上限，哪怕是一个很松很粗略的上限！