格凸多面体的分类及算法

来源 :北京大学 | 被引量 : 0次 | 上传用户:yu351464325
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
1899年,G.Pick发现了平面上关于格多边形的Pick定理,这是关于格多边形格点数与面积的关系最早的结论之一.1967年,E.Ehrhart发现了著名的Ehrhart多项式定理,它描述了高维欧氏空间中格多面体体积与所含格点数之间的关系.在之后的几十年中,Ehrhart多项式受到诸多数学家的热切关注.随着计算几何在现代科技中的广泛应用,近些年围绕凸多面体的算法研究,比如多面体几何重建、求凸包和点搜索等问题的算法设计、及其计算复杂度的估计,受到越来越多的关注.但是,迄今为止,我们对欧氏空间中格凸多面体所内蕴的性质仍然知之甚少.  1980年,V.I.Arnold研究了平面上给定面积的格凸多边形的分类问题.之后,I.Bárány,J.Pach,A.M.Vershik和C.Zong等人对Arnold问题的类比推广进行了深入的研究,得到了给定体积的d-维格凸多面体等价类类数的阶的上、下界估计.  本文研究了中心对称①格凸多边形的Arnold问题和格点数给定的格凸多面体的分类问题,并首次提出一个求解该问题的计算机算法.该算法可在2-维欧氏空间中对给定面积或给定格点数情况下,完全求解格凸多边形等价类的代表元集合,进而得到其等价类类数的精确值.其中判别两个已知格凸多边形是否等价的算法适用于高维情形.  对给定面积或给定格点数的中心对称格凸多边形,和给定格点数的一般格凸多边形,我们得到了类似于V.I.Arnold,I.Bárány,J.Pach和A.M.Vershik的上下界.然而当w-l≥d≥3时,格点数恰为w的d-维格凸多面体的等价类类数是无穷的.这与Bárány和Vershik所得的上界在直觉上相矛盾.该现象说明在格点数给定时,分类结果在高维空间和2-维空间的情形有着本质的不同.  使用在本文首次提出的算法,借助计算机程序进行数值计算,我们得到了V2,m,K2,w及与它们类似的格凸多边形分类问题的等价类代表元集合,进而得到k(2;w),k0(2,w)和v(2,m)在w,m=1,2,…,36时的精确值.
其他文献
本文讨论一类带Beddington-DeAngelis功能反应的捕食者-食惧扩散模型非负常数平衡解的稳定性.首先研宄ODE系统中非负常数平衡解的稳定性和分支的存在性,其次考察线性自扩散系
该文除去序言是对问题背景、现状与作者工作的介绍,剩下的正文部分由两部分内容组成.这两部分内容均是进入九十年代以来,关于正算子逼近研究的几个最热门的课题.第一部分内容