关于平面上凸格点集的投影研究

来源 :北京林业大学 | 被引量 : 0次 | 上传用户:caipeng1999
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
任意中心对称的凸体(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中。
其他文献
身份认证和密钥交换是不安全分布网络通讯的中心问题。口令认证协议就是利用短的、容易记住的口令,实现身份认证和密钥交换。在本文中,首先设计了对称和非对称的两个口令认证和
k-路问题和k-树问题是两类组合优化问题。由于其与实际联系的紧密性,这两类问题更易引起广大研究工作者的关注。到目前为止,已得到了一些的理论研究成果,为实际应用奠定了理论基
判断一个图是否有哈密顿路的问题是图论中的一个经典问题,而判断一个图是否能被划分成一些给定数目路的并问题是哈密顿路问题的一个重要推广,后者被称为点不交路的划分问题。路
随着2004年新的巴塞尔协定的诞生,经济资本的计算及分配问题成为金融界讨论的中心问题。本文的主要目的是对经济资本进行最优分配,并考虑最优经济资本量的模型。文章首先提出了
本文研究了软硬件协同设计中的性能和资源问题,包括系统的资源和时间估计,软硬件划分的性能优化问题等,并把软件形式化方法应用于这个领域,取得了一些成果。 有了描述系统功能
本文关注的是对称本原矩阵.我们已知n阶对称本原矩阵指数集SEn={1,2,…,2n-2}S,其中S是[n,2n-2]中的全体奇数.目前,本原指数不小于n-2的对称本原矩阵的刻画已经完成.本文将运用图
班主任是班集体的组织者、管理者、指导者,是全面关心学生发展的主要教师和精神关怀者,也是促进学生健康成长的关键人物。本研究旨在探索新课改背景下中学班主任专业化发展的
2003年10月15日9时整,“神舟”五号载人航天飞船承载着一个古老民族的千年飞天梦,从内蒙古额济纳旗苍茫浩瀚的戈壁上腾空而起,直入苍穹……电波频传,举国欢庆,世人瞩目。沸
本文讨论了在一个常返的图上从同一点出发的两个独立的连续时间参数的简单随机游动是否能相遇无穷多次的问题。若能,则称该图具有无穷相遇性,否则,称该图具有有限相遇性。主要结
身份认证和密钥交换一直是信息安全领域的重要研究课题。基于口令认证的密钥交换(Password-AuthenticatedKeyExchange,简记为PAKE)在近几十年来得到了长足发展,同时又存在着许