基于平面的均匀分布和正态分布点集的凸包加速算法研究

研究怎样对于平面散乱点集进行的凸包算法的加速,主要的思想是计算一个点集的边界,摒弃边界范围内的点集,并且对于均匀分布和正态分布分别计算了最适合的加速因子,得到了平均意义上的O(n)的凸包算法.     

基于场表示的平面无序点集曲线重建算法

由无序离散点集重建出曲线曲面模型，在反求工程与计算机视觉中都有着广泛的应用。针对平面无序带噪声的曲线重建问题，通过模拟带电粒子在空间中形成场分布的现象，构造了一个反映平面点集形状与分布稠密程度的场函数，以场函数曲面的脊线在平面上的投影作为平面无序点集的重建曲线。为求得重建曲线，可先在平面上选取一条适当初始曲线，由初始曲线沿着场函数的梯度方向运动，其极限位置便为重建曲线。大量实例证明，这种方法简单可行，可获得满意的重建曲线；同时，对于带插值约束条件以及分布不均匀的点集，也可以获得满意的结果。     

基于四叉树结构索引的约束TIN的构建

提出了一个用四义树索引对平面区域进行划分并在此基础上用前沿推进法实现平面点集TIN构建的算法。对于实际应用中所遇到的数据，四叉树索引能够在有限层次内对平面区域进行有效划分，从而保证了TIN构建程序的运行效率。该算法能适用于任意的初始边界约束条件，并对边界和点集的分布特征具有良好的适应能力，因此该算法适用于复杂地形的DTM建模。     

基于有序简单多边形的平面点集凸包快速求取算法

凸包问题是计算几何的基本问题之一，在许多领域均有应用。传统平面点集凸包算法和简单多边形凸包算法平行发展，互不相干。本文将改进的简单多边形凸包算法应用于平面点集凸包问题中，提出了新的点集凸包算法。该算法首先淘汰掉明显不位于凸包上的点，然后对剩余点集排序，再将点集按照一定顺序串联成有序简单多边形，最后利用前瞻回溯方法搜索多边形凸包，从而得到点集的凸包。本文算法不仅达到了Ｏ的理论时间复杂度下限，而且算法     

求平面点集凸壳的一种新算法

在研究了大量的求平面点集凸包的算法基础上,提出了一种新的构造平面点集的凸壳算法。此算法先求出四个极值点,构造出一个四边形。对于四边形外面的点依次用二分法进行判断是属于哪个线段区域;对于一个线段区域上的点只需要找出右侧的点,分别和线段的两个端点连接得到新的多边形链,依次这样处理每个点,直到结束。这样就得到四个简单多边形单调链,然后对单调链求凸点,时间复杂度为O（n）,最后求得的每个凸点就是平面点集的凸壳,此算法总的时间复杂度不超过O（n log n）。     

平面点匹配的一点校准算法

点模式匹配是一项重要的视觉课题。对于一个平面点集,由平移和旋转并伴有一定噪声作用产生另一点集,提出一个基于一点校准的点模式快速匹配算法,并推广到带有属性点的匹配问题中。基于一点校准的点模式匹配算法,其计算复杂性为O(mn),其中m,n分别是两个点集所含点的个数,比基于两点距离近似相等的校准匹配算法,其计算复杂性为O(m2nl)(其中l为第二个点集中与第一个点集中任两个点的距离近似相等的平均个数),极大地减少了计算量。     

一种基于图的平面点集Delaunay三角剖分算法

本文提出了一种基于图的平面点集Ｄｅｌａｕｎａｙ三角剖分算法。该算法首先求出平面点集的欧几里得最小生成树，然后逐次加入一边构造三角形网格，最后按最小内角最大的三角化准则，通过局部变换，得到平面点集的Ｄｅｌａｕｎａｙ三角剖分。本文同时阐述了它的对偶图；平面点集的Ｖｏｒｏｎｏｉ图的概念和性质。     

计算平面点集凸壳的两种新方法

平面上有限点集的凸壳在土木工程及其它许多领域均有很多重要应用,计算几何中的很多应用问题都与凸壳有关.现有多种求平面上点集凸壳的方法,但这些方法要么算法非常复杂,要么编码及实现非常困难.介绍了两种求平面点集凸壳的新方法,它们具有算法思想简单且易于编码实现的优点.     

基于区域正交化分割的平面点集凸包算法EI北大核心CSCD

为解决实际工程应用中具有超大规模的平面点集的凸包计算问题,提出了一种基于点集所在区域正交化分割的新算法.利用点集几何结构的部分极点对平面点集进行正交化分割,以获取不相干的点集子集簇,再对所有点集子集分别计算其凸包极点,最后合并极点得到凸包点集.在不同层级的正交化分割过程中,根据已知极点的信息,逐层舍去对于凸包极点生成没有贡献的无效点,进而提高算法运行效率.在与目前常用凸包算法的对比实验中,该算法处理超大规模的平面点集时稳定性高且速度更快.     

平面点集的O（logN）步凸壳算法

本文提出了一个平面点集的凸壳点判断定理，并依此定理，设计了在改进的三维树网上用Ｏ（ｌｏｇＮ）步就可找到平面点集（有Ｎ个点）的所有凸壳点的并行算法。     

球隙迁移算法实现全局优化

给出一种新的优化算法:球隙迁移法.该方法不是已有方法的融合或改进,它利用搜索过程中积累的极小点分布信息形成球隙,以此启发、指导后来的搜索区域,不但逃离了当前局部极小,还能有效地避免重复历史上的多个局部极小.目前的智能算法中,勘探和开采行为相耦合,球隙法实现了勘探与开采的分离,避免了相互干扰,减小了代价,对变量耦合对象的优化效果好.文中证明了球隙法能在有限计算次数内确定地找到连续函数的全局最优.     

星形2-hub选址问题的多项式时间算法

Hub作为特殊的设备在交通运输、邮政和电信网络中承担着交换、转载和整理的重要角色。研究一般网络中最小费用星形2-hub选址问题和最小时延星形2-hub选址问题,分别给出多项式时间算法,计算出2个hub的最佳位置。     

一种基于修正系统预测输出的自适应控制算法

本文利用预测误差的历史数据修正系统的预测输出,以抑制模型失配的影响.给出了修正的最小方差调节器和广义最小方差控制器的算法,并分析了所给修正算法能增强系统鲁棒性的机理.仿真结果表明了本算法的有效性.     

基于Web日志文件的关联规则挖掘模块的实现

在对Web应用挖掘的基本步骤作系统性研究的基础上,设计了一个基于Web日志文件的关联规则挖掘模块。该系统应能够对用户访问Web时服务器方留下的访问记录进行挖掘,从中得出用户的访问模式和访问兴趣。为了识别用户浏览模式,实现了利用关联规则挖掘算法Apriori对Web应用挖掘过程中预处理阶段所产生的用户会话文件进行挖掘的模块,该模块针对用户选定的若干页面产生满足最小支持度和最小置信度的页面之间的强关联规则,并以文本的形式显示挖掘的结果。     

全局优化的一类新的F-C函数

针对求解全局优化问题,有很多种求解方法。文中提出了一种快速求解一般无约束最优化问题的辅助函数方法。即F-C函数方法。该方法与填充函数法和跨越函数法相比较,既有相同点又有不同点。F-C函数法最大的优点就是在极小化F-C函数阶段中只需要进行一次局部极小化算法就能得到比当前极小值更低的目标函数局部极小点。文中在无Lipschitz连续的条件下,给出了一类新的求解全局优化问题的F-C函数。文中讨论了该F-C函数的优良性质并对该函数设计了相应的算法。最后,通过数值试验表明该F-C函数方法具有有效性和可行性。     

图的Steiner最小树问题的降阶回溯算法

图的Steiner最小树问题是经典的组合优化问题,是一个NP难题,在不同的领域有着广泛的应用。研究该问题的部分数学性质,在此基础上给出了该问题的初步降阶方法和下界子方法,形成一个新的回溯算法。该算法具有较低的时间复杂度,还给出了应用实例及其分析。     

基于水平集的新型彩色图像分割算法

由于考虑的泛函变分形式是非凸性质,向量值图像分割模型的计算结果经常会陷入局部最小值。基于活动轮廓的向量值图像的全局图像分割方法,以新型变分形式将向量值图像分割和图像去噪融入具有全局极小能力泛函框架中。新模型具有容易构造和较少计算量的特点,对比经典的水平集方法,可以避免繁琐的距离重复化水平集过程。通过对人工图像和真实图像进行分析,验证新方法具有更好的图像分割效果。     

Time-optimal control of a self-propelled particle in a spatiotemporal flow field

We address a minimum-time problem that constitutes an extension of the classical Zermelo navigation problem in higher dimensions. In particular, we address the problem of steering a self-propelled particle to a prescribed terminal position with free terminal velocity in the presence of a spatiotemporal flow field. Furthermore, we assume that the norm of the rate of change of the particle's velocity relative to the flow is upper bounded by an explicit upper bound. To address the problem, we first employ Pontryagin's minimum principle to parameterise the set of candidate time-optimal control laws in terms of a parameter vector that belongs to a compact set. Subsequently, we develop a simple numerical algorithm for the computation of the minimum time-to-come function that is tailored to the particular parametrisation of the set of the candidate time-optimal control laws of our problem. The proposed approach bypasses the task of converting the optimal control problem to a parameter optimisation problem, which can be computationally intense, especially when one is interested in characterising the optimal synthesis of the minimum-time problem. Numerical simulations that illustrate the theoretical developments are presented.     

LR最小替换集求解算法研究

文中对Ｄ．Ｍａｉｅｒ提出的关于关系数据库中的ＬＲ最小集的结构进行了分析，提出了一个比“ＬＲ最小集”更为简化的ＦＤ集的覆盖－ＬＲ最小替换集。给出了一个求ＬＲ最小替换集的多项式时间算法。修正了Ｄ．Ｍａｉｅｒ在其文中给出的一个ＦＤ集为最优覆盖的必要条件。     

无双语词典的英汉词对齐

该文提出了一种基于语料库的无双语词典的英汉词对齐模型．它把自然语言的句子形式化地表示为集合，通过集合的交运算和差运算实现单词对齐，同时还考虑了词序和重复词的影响．该模型不仅能对齐高频单词，而且能对齐低频单词，对未登录词和汉语分词错误具有兼容能力．该模型几乎不需要任何语言学知识和语言学资源，使语料库方法可独立应用．实验表明，同质语料规模越大．词对齐的正确率和召回率越高．