论文部分内容阅读
任意中心对称的凸体(n维欧氏空间Rn中含有非空内点的紧凸集)都可以被其投影唯一决定(在相差一个平移的意义下)。这是凸几何中著名的Aleksandrov投影定理。相应于Aleksandrov投影定理,R.J.Gardner、P.Gronchi、C.M.Zong提出了离散化的Aleksandrov投影问题,即在n维整数格点空间中,中心对称的凸格点集是否可以被其投影计数唯一确定?随后经过J.Zhou、H.Xiong的研究,表明在中心对称的凸格点集中,当所有格点的y坐标绝对值小于等于2且格点数不为11时,这样的凸格点集可以被其投影计数唯一确定(在相差一个平移的意义下)。在这些研究中所涉及到的凸格点集都具有一定的限制条件,为了对离散化的Aleksandrov投影定理进行更为一般的研究,本文从算法的角度主要考虑了一般的凸格点集投影点数的计算问题。在论文中,首先使用坐标矩阵表示凸格点集,并探讨坐标矩阵的性质;然后对于任意给定的素方向,结合平面扫描算法、排序算法等算法思想,找到了一种有效的算法用于计算二维中心对称的凸格点集在任意素方向上的投影点数,并对算法的时间复杂性进行分析。此外,凸体K的任意d维投影均相应的可以放入凸体L的d维投影中(在相差一个平移的意义下),那么凸体K是否能够放入凸体L中(在相差一个平移的意义下),本文考虑了D.Klain提出的如上问题的离散化情况,结合多边形的欧拉定理及其推论确定二维平面上包含n个格点的凸格点多边形P,当n和P满足一定条件时可以通过平移和旋转放入包含n-1个格点的凸多边形Q中。