低复杂度高度场的通视性研究及快速光照计算

为快速判断高度场场景点的通视性和可见范围, 满足交互式应用的需要, 提出低复杂度高度场基于可见二叉树的凸包树简化方法。通过对高度场数据在8个方向的线性扫描, 确定每个高度场数据点的最大方位角, 构造凸包树型结构; 对凸包树信息进行分析, 构造可见性二叉树作为方向扫描存储结构, 在光照计算过程中有效提高可见点的搜索算法效率; 结合阴影图的间接光照计算, 实现了交互式帧率的动态低复杂度高度场绘制效果模拟, 降低计算成本。     

寻求中国货郎担问题最短回路的多项式时间算法

研究求解中国货郎担问题最短回路的多项式时间算法。首先利用计算机几何凸壳与中轴的结构将集划分尤其中干个子点集,然后反复采用求子点集凸壳及划分科余子点集的方法,求得通过子点集的子路径,最后将各子路径连接成一条回路。中国货郎担问题存在多项时间算法求得最短回路。     

环状分布平面点集的凸包快速生成算法

针对栅格辅助法在处理环状分布平面点集时计算效率较低的问题,提出了一种格网2次处理算法.通过比较离散点所在网格的空间位置关系,经2次剔除点集中绝大部分不可能成为凸包顶点的内点,减少了参与Graham扫描的点数,提高了计算效率.实验结果表明,与栅格辅助法相比,格网2次处理算法能够明显提高处理环状分布平面点集的效率,而且对于其他空间分布较为均匀的平面点集的处理效率也有一定程度的提高.     

基于夹角的二维凸包改进算法

二维凸包问题是计算几何领域的经典问题之一,在地理信息系统中有广泛的应用.在凸包中,位于两凸点之间直线上点也在凸包上,但不是凸点,如何寻找凸点是凸包算法的关键.提出了基于夹角的平面点集凸包改进算法,以最大夹角,按顺时针的方向可得到所有的凸点,当满足最大夹角的点不唯一时,以离当前凸点最远的点为凸点.     

一种基于凸壳的智能服务机器人路径规划算法

将一种基于凸壳的路径规划算法应用于体育场智能服务机器人,首先采用基于Haar特征分类器的方法确定球的坐标,采用基于颜色模型的方法确定机器人的位置及航向,并根据机器人的自身特点,将一定范围内的多个球视为一个目标点处理;然后以目标点坐标作为算法输入,采用基于凸壳的路径规划算法得到一条较优的捡球路径.该算法可以降低机器人的捡球运动代价,有效提高机器人的捡球效率.     

GIS中散乱点集凸包的快速算法及编程

在地理信息系统(GIS)中,不规则三角网(TIN)的生成及数字地面模型(DTM)的建立都会用到点集凸包的计算.通过研究了传统凸包算法,并对其进行改进,提出简单快速的点集凸包改进算法.经过验证,新算法可准确快速地求出点集凸包.     

一个安全电子商务身份验证协议

针对电子商务活动中存在的冒名欺诈问题，设计了一个安全的电子商务身份验证协议。协议的安全性是建立在目前尚未存在有效攻击方法的有限域上非超奇异椭圆曲线的椭圆曲线离散对数问题之上的。从理论上分析，该协议是安全的并具有一定的实用价值。为了提高协议在实际应用当中的运算速度，设计了实现该协议的椭圆曲线密码体制基本算法，这些算法具有形式简单，运行速度快的特点，完全可以满足实际应用的需要。     

考虑边界约束的DTM三角网模型生成算法研究

无约束的数字地面模型(DTM)空间三角网算法生成的三角网外围边界是一个凸壳,这对于实际区域为凹多边形的区域(如公路弯道)会有较大的模拟失真.文章提出一种改进的算法,通过分析实际边界多边形的精细度影响因素,导出确定区域相邻离散点平均边长的计算方法,进而确定一个边界多边形边长的最大值.以该边长最大值对无约束的三角网外围边界...     

基于代数等价路径的一类线性约束凸规划问题的内点算法

对于满足尺度李谱希茨条件的一类线性约束凸规划问题,提出了一种基于代数等价路径的原始-对偶内点算法,并讨论了计算复杂性.该算法可以在任一内部可行点启动,并且全局收敛,当初始点靠近中心路径时,此算法便成为中心路径跟踪算法,总迭代次数为O(nL),其中L是问题的输入长度,数值实验结果表明算法是有效的.     

旅行推销员问题凸包方法的性能比分析

在欧几里德平面上证明了旅行推销员问题的凸包方法的性能比上界为n／2,同时给出了凸包随意插入算法的性能比可以接近n／2的例子。另外,对凸包增量最小插入法、凸包最近插入法及凸包最近加入法给出了性能比不超过3的证明。     

向量优化中Arrow-Barankin-Blackwell稠密性定理的评注

 真有效点集在Pareto有效点集中的Arrow-Barankin-Blackwell稠密性理论是向量优化理论的组成部分,已被广泛研究并获得了一系列深刻的结果.该文就弱紧凸集和紧凸集概述了正真有效点集在Pareto点集中的稠密性,并就弱紧非凸集介绍了超有效点集在Pareto点集中的稠密性.     

Demyanov差的两个运算

Demyanov差是非光滑分析与优化,尤其是拟可微分析与优化中的一个重要概念．基本的运算法则已经形成,包括加法运算、效乘运算、加法的消去律等．但是,其中部分公式是用包含关系表达的,这给使用造成了很大的不便．为此给出了两个关干Demyanov差的新的用等式表述的运算法则：两个彼此互补的凸紧集对的和的Demyanov差,有限个凸紧集的凸包和与这些凸紧集正交互补的凸紧集的Demyanov差．这两个法则可以用于计算和函效和极大值函数的次微分与超微分的Demyanov差,从而有助于表述既含等式约束,又含不等式约束的拟可微优化的最优性条件．     

计算Delaunay三角剖分的新算法

提出一种计算K维欧氏空间EK 中任意数据点集的凸包的Delaunay三角剖分的新算法 .通过引入辅助的无穷三角形和在全空间 EK 的Delaunay三角剖分 ,确保最终结果是数据点集的凸包的完整Delaunay三角剖分 ,而且使算法具有在线性质 ,适用于动态的数据点集 .     

寻求多边形链顶点凸壳的算法

提出一种计算简单多边形链顶点凸壳的算法，基本思想是分段计算，在每段的计算中，先分4种不同情况计算出边链L1，然后利用一种技巧将L1上的部分顶点排列成顶点角递增序列，构成边链L2，最后对L2进行倒查，删去非凸壳顶点，剩下的点即凸壳顶点，该算法不仅易于实现，而且其时间复杂性是线性的。     

一种理性安全协议形式化分析方法及应用

博弈逻辑ATL和ATEL可以对传统安全协议的公平性、安全性等性质进行分析与验证.不过在理性环境下,由于参与者对知识的自利性,ATL和ATEL都不适合形式化分析与验证理性安全协议.于是在并行认知博弈结构CEGS中引入效用函数和偏好关系,得到新的并行认知博弈结构rCEGS,并在合作模态算子《Γ》中引入行为ACT参数,提出新的交替时序认知逻辑rA-TEL-A,并基于不动点描述rATEL-A时序算子.然后基于rATEL-A,提出适合于形式化分析理性安全协议的推理系统,并对具体的理性安全协议的公平性、安全性等性质进行形式化分析.     

Secure multi-party computation solution to Yao''s millionaires'' problem based on set-inclusion

Secure multi-party computation is a focus of international cryptography in recent years. Protocols for Yao's millionaires' problem have become an important building block of many secure multi-party computation protocols. Their efficiency are crucial to the efficiency of many secure multi-party computation protocols. Unfortunately, known protocols for Yao's millionaires' problem have high computational complexity or communication complexity. In this study, based on the 1-out-of-m oblivious transfer and set-inclusion problem, we propose a new protocol to solve this problem. This new protocol is very efficient in terms of both computational and communication complexities. Its privacy-preserving property is also proved by simulation paradigm which is generally accepted in the study of secure multi-party computation. We also compare the information leakage of our new protocol and the known protocols.     

复杂采空区三角网模型剖面轮廓线提取方法

 采空区是矿山安全生产面临的主要灾源之一,准确获取采空区剖面等信息是实施采空区灾害防治及空区周边资源安全开采的重要基础,而采空区三角网模型剖面轮廓线提取是采用可视化方法实现采空区剖面准确获取的前提。在分析目前常用的三角网模型剖面轮廓线提取方法（即最小距离法、扇形区域法和凸包算法）运用于提取边界复杂的采空区剖面轮廓线时存在缺陷的基础上,对传统的方法进行了改进,形成了适用于复杂边界采空区三角网模型剖面轮廓线的提取方法--凸包压入法。首先以垂直于任意坐标轴的平面剖切采空区三角网模型得到轮廓线的无序点集,提取无序点集的凸包线作为初始轮廓线,然后将包络于初始轮廓线内的点按张角最大的原则全部添加到轮廓线中,获得完整的剖面轮廓线,形成采空区剖面。实际应用表明,研究形成的算法能够快速有效地提取复杂采空区的剖面轮廓线,可准确获取复杂采空区剖面,具有很好的实用价值。     

有关保护私有信息的三角不等式判定问题研究

安全多方计算是信息安全领域研究的热点问题之一,保护私有信息的三角不等式判定问题是一类基于三方的特殊安全多方计算问题。文章设计了一个基于Paillier加密算法的百万富翁比较协议,并扩展该协议至三方参与者,形成一个基于Paillier加密算法的三角不等式判定协议;结合点积协议与百万富翁协议,设计了一个保护私有信息的三角不等式判定协议,在保护用户私有输入信息的条件下,解决了三角不等式的判定问题。     

基于点云数据的株冠体积测量方法

 在林业领域,利用地面三维激光扫描(Terrestrial 3D Laser Scanning,TLS)技术可获取测树因子,以辅助林业资源调查,但该技术尚未用于测量灌木植物的体积。在介绍TLS系统组成、工作原理的基础上,基于紫穗槐的点云数据,测量29株两年生紫穗槐苗的冠高、冠幅直径,采用整体凸包算法、切片凸包算法、切片分割算法和立体栅格算法计算紫穗槐的株冠体积,并对株冠体积与冠高、冠幅直径进行相关性分析,从而选择适合测量灌木植物体积的方法。结果表明,立体栅格算法是计算与紫穗槐有相同结构特征植物株冠体积的最好方法,利用TLS技术可监测野外灌木生长状况。     

基于散乱点集空间划分的凸壳体快速生成算法

针对凸壳体特征的三维散乱点集数据,在空间划分结构的基础上进行K近邻搜索并估算点的法向量.引入点邻域的离差计算来代替曲率计算,提取边界区域特征点集,并比较分析了两种方法的效果.最后对提取后的剩余点集进行基于法向量的分块及拟合,并在可视化工具箱(VTK)中进行布尔运算,实现凸壳体模型的生成及可视化.该方法在双底双壳船舶液舱点集数据中进行了验证.