论文部分内容阅读
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时的精确值.