关于任意多边形可三角剖分性的归纳法证明合理性验证问询
关于任意多边形可三角剖分性的归纳法证明合理性验证问询
大家好,首先我先定义一些术语避免误解(可能有点啰嗦,见谅):
- 考虑由有限条连续平面线段组成的集合,无内部交点且构成简单闭合曲线。这类曲线将平面分为有界区域和无界区域。我们定义n边形为包含该有界区域的这类曲线,多边形P的周长就是上述的闭合线段。
- 多边形P的**三角剖分(不添加额外顶点)**是将其划分为一组三角形,这些三角形与P共享所有顶点,且两两内部不相交,它们的并集就是P本身。
接下来是我的问题:任意多边形是否都可以被三角剖分?
我稍微查了一下资料,发现这其实是Max Dehn著名的2-Ear定理的推论,答案是肯定的。不过我自己想了一个归纳法的证明思路,想请大家看看是否可行:
归纳法证明思路
- 基础情况:3边形(三角形)的三角剖分是显然成立的,本身就是一个三角形。
- 归纳假设:假设所有边数为3、4、…、n-1的多边形都可以被三角剖分,现在考虑一个n边形P。
- 首先,P至少有一个凸角∠ABC,否则P会是无界的(这一点是成立的,因为简单多边形必然存在凸顶点)。
- 最初的思路:在∠ABC内部可能存在其他顶点,我打算选择其中到顶点B欧氏距离最近的点;如果有多个这样的点,再选最靠左(或最靠右)的那个,记为B'。此时线段BB'是P的一条对角线,它将P的周长分成两部分:BC…B'和BB'…A,对应的边数分别为l和m(l,m < n-1),显然n = m + l。这样得到的两个子多边形BC…B'(l+1边形)和BB'…A(m+1边形)的边数都小于n,根据归纳假设它们可以被三角剖分,因此P也可以被三角剖分。
不过在收到@Jaap Scherphuis的一些非常有用的评论后,我对证明思路做了修改:
编辑后的证明思路
在证明中,不再选择距离最近且最左/最右的顶点,而是做如下操作:从顶点B出发,以线段BC为起始边作一条射线,将这条射线向内旋转,直到它碰到P的某个顶点(可能碰到多个)。从这些被碰到的顶点中,选择距离B最近的那个,记为b。后续的证明步骤和之前一致:线段Bb是对角线,将P分成两个边数小于n的子多边形,根据归纳假设它们可被三角剖分,因此P也可以。
请问这个修改后的思路是否可行?谢谢!
备注:内容来源于stack exchange,提问作者dmtri
相关产品推荐
相关产品推荐

