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