基于C++浅谈几何学与计算机的交叉应用【100011493】

# 浅谈几何学与计算机的交叉应用 # 一、摘要 就计算机在几何学领域的应用,本文介绍了四色定理(Four Color Theorem)及其历史与机器证明,以及四色问题的求解.就几何学在计算机领域的应用,本文介绍了三维凸包(convex hull)表面积问题的求解. 关键词 四色问题;凸包 # 二、正文 国家的发展离不开日益密切的国际经济文化交流,学术也是一样.如今,学科交叉一词时常出现在我们眼前. 在进行数学科学的研究时,市场需要计算机辅助；在进行计算机科学的研究时,常常需要转化称数学问题 进行求解.如四色定理,开普勒猜想,NP-硬度的最小权重的三角测量,布尔毕达哥拉斯三元组问题等著名数学难题,均借助计算机得以证明；如凸包求解,时间复杂度(time complexity)计算,空间复杂度(space complexity)计算等问题. 几何学是数学的一大分支,本文将就四色定理和凸包求解问题,浅谈几何与计算机的交叉应用. 四色定理四色定理,又称四色猜想,是世界三大数学猜想之一.  四色地图的一个例子 ## 2.1 定理内容 如果在平面上划出一些邻接的有限区域,那么可以用四种颜色来给这些区域染色,使得每两个邻接区域染的颜色都不一样. 另一种通俗的阐述任意一个无外飞地(exclave)的地图都可以用四种颜色染色,使得没有两个相邻国家染的颜色相同.其中,外飞地为人文地理中的外飞地概念.若某国家 A 拥有一块与本国分离的领土 a , a 被其他国家包围, 则 a 称为 A 的外飞地.  外飞地的一个例子拓扑学阐述设有一平面或其一部分,将其划分为互不重叠的区域的集合. 定义地图:一个地图为以下方式的划分: 将平面划分为有限个区域,使得任意两个区域的交集是空集,所有的区域的并集是整个平面;所有区域中,只有一个区域是无界区域,其余区域都是有界区域. 其中,有界区域指能够用一个长和宽都有限的矩形覆盖的区域;无界区域则是指不能用这样的矩形覆盖的区域.每个区域相当于通俗说法中的国家.区域之间的边界相当于通俗说法中的国界线,定义为连续不自交的曲线,也称为连续简单曲线. 连续简单曲线是指一个连续函数: [0,1] → R2的像集= {c(t)∣t ∈ [0,1]},且满足= c(t2) ,0 t1 < t2 1,(t1 ,t2) = (0,1), 这样说明曲线不与自身相交.若 c(0) = c(1), 则称曲线为弧,否则称为圈.平面 R2 中的一个地图是指一个有限个连续简单曲线的集族 m= { Ci} ,m ∈ N ∩ [2,+∞).i=1 其中对 i = j ∈ N ∩ [1,m],Ci = {ci( t)∣t ∈ [0,1]}是连续函数ci : [0,1] → R2的像集,且满足ci( t1) = ci( t2) ,0 t1 < t2 1,(t1, t2) = (0,1),且∣Ci ∩ Cj∣ ∈ {0,1}. 定义边: L 中每一个连续简单曲线. 定义顶点:任意边 C 的端点 c(0),c(1) 称顶点. 定义中性点: 所有属于边或顶点的点.其集合NL = {x∣x ∈ Ci,i ∈ N ∩ [1,m]}. 定义国家: L 将非中性点划分成的若干个道路连通的开集.其集族 AL. 可见,每个国家是 R2 NL 的一个极大连通子集,是没有外飞地的;取一个非中性点 x, 所有能够从 x 经过一条不含中性点的弧到达的点构成的集合,就是一个国家.定义 n-染色:地图 L 的一个 n-染色方案指一个函数: AL → N ∩ [1,n].若Ai) = f(Aj) ,Ai, Aj ∈ AL,  则称它是可行的.四色定理:每个地图都存在可行的 4-染色方案,即L,f : AL → {1,2,3,4},s.t.,f(Ai ) = f(Aj) ,Ai, Aj ∈ AL ,  #### 图论阐述 将上述地图转化为图论中的一个无向平面图,即地图中的每一个国家用其内部的一个点代表,作为一个顶点.如果两个国家相邻,就在两个顶点之间连一条线.  地图与无向平面图互相转化的一个例子 四色定理:必然可以用四种颜色给无向平面图的顶点染色,使得相连的顶点颜色不同. ## 2.2 历史 年,古德里(Francis Guthrie)提出猜想:"只需要四种颜色为地图着色".年,肯普(Alfred Kempe)宣称证明了四色定理.11 年后,肯普的证明被希伍德(P. J. Heawood)推翻.他举出了反例,并提出了五色定理.但近代,该反例又被董德周推翻. 伯克霍夫(George David Birkhoff)证明了由不超过 12 个国家构成的地图都能用四色染色.9 年后, 他的学生富兰克林(Philip Franklin)证明了由不超过 25 个国家构成的地图都能用四色染色,阿佩尔(K. Appe)和哈肯(W. Haken)使用计算机辅助证明了四色定理 ,但是他们的证明在当时并未获得普遍认可.主要原因为使用计算机的部分无法用手算核实,应该用手算核实的部 分因过于繁琐,无人能够独立完成.,西缪尔(P. Seymour)等人对阿佩尔和哈肯的证明进行了修正和改进,同时证明了其正确性.龚提尔(Georges Gonthier)使用证明验证程序 Coq 来对当时交由计算机运算的算法程序进行了形式上的可靠性验证.验证表明,四色定理的机器验证程序确实有效地验证所有构形的可约性,完成了证明中的要求. ## 2.3 计算机辅助证明 ### 2.3.1 可约构形 考虑 n + 1 个国家中邻国数目最小的国家 A , A 的邻国的数目不超过 5. 若 A 的邻国数目不超过 3, 那么可以把 A 去掉(如和其中一个邻国连成一体),形成一个 n 个国家的地图,这个地图可以用四种颜色着色, 而原来的 3 个邻国至多用了三种颜色.这时候将 A 还原,染上第四种颜色,就等于找到给用四种颜色原地图着色的方法. 这种能够去掉一个国家,减少国家数的局部称可约构形(reducible configuration). ### 2.3.2 不可避免的可约构形集 伯克霍夫等人的证明是肯普的方法的延续和系统化,归纳为寻找一个不可避免的可约构形集(an unavoidable set of reducible configurations,简称不可避免集).  肯普使用的不可避免集 ### 2.3.3 放电法 将无向平面图其看作是平面的电网,并将每个点按照度数(degree,连出的边数)分类.首先在每个度数为 k 的节点放置 6 k 的电荷. 放电过程(discharging procedure)指将这些电荷以特殊的规则进行重新分配,从而找出电网结构上的特性,创建不可避免集.具体来说,可以假设某些构形全不存在,然后构造一个放电过程,使得接受电荷的总量不再等于释放电荷的总量,从而导出矛盾.每个良好设计的放电过程都能证明一个不可避免集的存在. 阿佩尔和哈肯的证明二人通过纸笔运算,得到了一个由 1936 个构形构成的不可避免集,对应的放电规则由 487 条规则构成.经过电脑 1200h 的验证,得出这 1936 个构形均为可约构形,四色定理得证. ### 2.3.4 西缪尔等人的证明 经过修正和改进,不可避免集大小减至 633 ,放电法则减至 20 个,图着色算法由 4 次时间算法优化为 2 次时间算法,证明所需机时由 1200h 缩短到 24h .此外,第二代证明达到了人工复核的要求,如果用计算机验证只需 5min 就能完成,且没有第一代证明中只有计算机才能完成的验证过程. ### 2.3.5 机器证明的可靠性问题 龚提尔(Georges Gonthi