DVE场景精简的NP-Hard问题及其近似算法

高效的网格精简算法对于大规模DVE场景的实时绘制与传输均十分重要.目前已经提出了大量关于网格精简方法[1],但绝大多数网格优化算法都是面向实际应用的.我们却从计算机科学理论的角度出发,对这一经典问题重新进行了深入研究.首先,我们发现网格精简是一个最优顶点覆盖问题,即NP-Hard问题.然后,我们又提出了一种基于贪心算法的用于网格精简的最优顶点覆盖问题的近似算法.理论推导与实验数据都说明本文所给出的近似算法有效地减少了DVE场景的网格数量,能进一步提高DvE场景数据的网络传输速度.     

基于GPU的加权Voronoi图计算

Voronoi图描述了一种对空间按照欧式距离进行的划分,是关于空间邻近关系的一种基础数据结构,在图像处理、城市规划以及地理信息系统等应用中有着重要的地位.顶点加权Voronoi图是Voronoi图的一种扩展,有着更为广泛的应用,但由于其实现的复杂性,相关算法一直比较少.为此,提出了一种基于GPU的加速算法.该算法利用GPU的高效计算特性,能够实时地生成离散的加权Voronoi图.与现有的算法相比,该方法易于实现,同时实验显示算法具有更好的计算性能.     

基于图的悲观多粒度粗糙集粒度约简

结合图的顶点覆盖理论,探讨了悲观多粒度粗糙集粒度约简的新方法.首先提出悲观多粒度粗糙集诱导图的概念,并给出其粒度约简的图特征,在此基础上,以图的方法刻画粒度的重要度,进而设计基于图的悲观多粒度粗糙集粒度约简的算法;其次,定义悲观多粒度决策粗糙集诱导图的概念,类似地给出其粒度约简的图特征和粒度重要度,设计基于图的悲观多粒...     

机场登机口分配问题的顶点着色模型与算法

对航班-登机口分配问题进行研究,将其看成顶点着色问题进行求解,设计了简单有效的可以应用于具有卫星厅的登机口分配的贪婪算法策略.将按照"先到先服务"的原则,依次运用启发式规则为当前航班选择登机口,即优先使用可供航班类型种类数量少的登机口,并选择已空闲时间最长的登机口.这样有助于减少使用可供多种类型航班使用的登机口的数量,...     

仿射李代数sl(2,(C))的顶点算子表示VQ上的顶点代数结构

根据李代数的表示理论,研究了仿射李代数sl(2,(C))的顶点算子表示VQ的顶点算子结构,通过形式级数的计算方法,证明了VQ是一个顶点算子代数.     

超欧拉图判定方法的一个注记

通过对图的奇顶点的导出子图做研究,得到了由奇顶点的导出子图的性质判定图的超欧拉性的方法,即当图的奇顶点的导出子图满足一定性质时,可得出图的超欧拉性.     

含悬挂点自补图的递推构造

设Ｇ是ｐ阶自补图，文中讨论了含悬挂顶点的ｐ＋４阶自补图与所有ｐ阶自补图的关系，给出了由ｐ阶自补图构造出ｐ＋４阶含悬挂顶点的自补图的方法及含悬挂点的ｐ＋４阶自补图的数目Ｎ１（ｐ＋４）．     

顶点泛圈图的一个充分条件

本文给出了无爪图是顶点泛圈图的一个充分条件,推广了Brocrsma和Veldman的两个结论。     

亲切图的性质及其应用

给出了亲切图的构造方法、性质、应用和几种特殊图的亲切标号。     

均匀三次B样条曲面顶点反求的整体算法

本文推导出一个由均匀三次B样条曲面上型值点反求网格顶点的整体算法公式,明显地展示出型值点与网格顶点间的函数关系.如果给定曲面上m×n个型值点,再按边界条件给最外层网格顶点赋值,则其余m×n个网格顶点全部可由该式解出.计算过程很简单.克服内存不足的几种措施也在此作了介绍.