低代价最短路径树快速算法的时间复杂度研究

低代价最短路径树是一种广泛使用的多播树,它能够在保证传送时延最小的同时尽量降低带宽消耗.快速低代价最短路径树算法FLSPT是在DDSP算法的基础上,通过改进节点的搜索过程,该算法构造的最短路径树与DDSP算法构造的树具有相同的性能,但其时间复杂度低于DDSP,其时间复杂度为O(nlog n e).FLSPT是利用Fibonacci堆来选择图中未计算点的最小值来计算时间复杂度的.通过对FLSPT的程序和Fibonacci堆的分析发现,用O(log(n!) e)来表示FLSPT算法的时间复杂度比文献[6]中分析的O(nlog(n) e)更能体现FLSPT算法高效率.     

近似线性平均复杂性的平面点集Voronoi图增量算法的设计与实现

1 引言 Voronoi图是计算几何学科的一个重要结构,在模式识别、计算机图形、计算机辅助设计等领域有广泛的应用。平面点集Voronoi图的常用构造算法有三类:分治法、平面扫描法和增量算法。由于增量算法不仅适用于静态点集,而且还适用于动态点集,因而受到重视。 Voronoi图增量算法中的关键工作是最近邻的选择和搜索。已有算法大都采用随机穷举法,因而效率较低。本文首先介绍了Voronoi图的翼边数据结构表示方法,在增量算法时间复杂性分析的基础上,提出了应用桶技术选择生成子并提     

基于凸片段分解和格网的点在多边形中的可见边检测

检测点在多边形中的可见边是计算几何中的一种基本计算,文中对此提出一种加速算法.首先对多边形进行凸片段分解,以利用点在凸多边形中可见边的快速计算;然后利用格网结构实现由近及远的计算,避免处理被遮挡的凸片段.该算法可基于格网结构方便地进行并行处理,并可统一处理含空洞和不含空洞的多边形,其预处理时间复杂度为O(n),空间复杂度也是很低的O(n),而检测的时间复杂度在O(logn)～O(n)之间自适应变化,其中n为多边形的边数.     

增量构造Voronoi区域的改进算法

将Voronoi区域的半平面公共交集转换为Voronoi顶点与半平面的位置关系,提出一种简单的裁剪规则实现Voronoi区域的增量构造;该算法可以有效地处理半直线Voronoi边与直线Voronoi边以及节点共线等特殊情况。理论分析与实验结果表明,该增量构造Voronoi区域的平均时间复杂度是近似线性的。     

一个基于Voronoi图的最小三角形的近似求解算法

在一个平面中有n个点,求解由这n点中任意3个点所组成的三角形中面积最小的三角形。很显然,可以简单地以穷举法计算出结果,但是,穷举法在这个问题的求解过程中的时间复杂度为O（n3）。提出一种基于Voronoi图的最小面积三角形的近似求解算法,其中时间复杂度是O（nlogn＋2n-5）。基本思想是分治法的思想,也就是把平面进行区域划分,把大问题转化成多个小问题来求解。     

一种基于移动IPv6路由寻址的最短路径优化算法

移动IPv6的路由寻址是一个最短路径优化问题,最著名的两种最短路径算法是迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd)算法,这两种算法的时间复杂度都是O(n3).本文通过对这两种经典算法的研究与分析,提出一种求最短路径的优化算法.该算法的时间复杂度是O(e*n),在连通图中,该算法能够比Floyd算法少近50%的迭代次数,在非连通图中e<相似文献   

利用Voronoi图改进离散数据重构曲面算法

本文利用Delaunay三角剖分和 Voronoi图的性质,实现了一种对散乱点重构闭合曲面的方法。该方法在搜索策略上进行了改进：首先对输入点进行三角剖分,产生相互独立的四面体,构建一个凸包;然后利用Delaunay三角剖分产生Voronoi图;最后根据Voronoi图的性质,选择包含在形体内部的四面体,提取出边界三角形,完成散乱点边界重构。计算复杂度和Delaunay四面体数量成正比,在自动形状重构时形状边界提取过程的计算复杂度为O(n),算法适用于各种涉及图形重构的工程应用。     

入侵检测系统中高效的模式匹配算法

针对入侵检测系统模式匹配效率低的问题,提出一种高效的模式匹配算法.该算法通过对模式进行预处理记录模式的信息,然后对子节点进行递归比较,找到重复度最大的部分,提高模式匹配的效率;通过增加附加m个节点的匹配模式结构,降低模式匹配算法的时间与空间复杂度.理论分析表明,对于包含n个节点的主题树,提出的模式匹配算法的时间复杂度为O(nlog2n+mlog2m),空间复杂度为O(n+m).详细的实验以及与现有算法的比较表明,提出的模式匹配算法在时间、空间和匹配率性能上具有更高的效率.     

利用类Delaunay三角剖分实现Voronio图

1 引言计算几何在计算机辅助设计、计算机图形学(特别是三维图形生成技术)及机器人等领域是非常重要的。特别在近年来,受到了学术界的极大关注。Voronoi图是计算几何的一个重要分支。在气象、生态、空中交通管制、城市规划等领域都得到广泛应用。至今已发展了大量的实现Voronoi图的方法,发表了很多文章,基本上是基于连续域计算几何出发进行的,其计算方法主要分成两个类型:一个是增量算法,通过每次增加一个点来计算Voronoi图;另一种是分合算法,通过将点划分成两部分,递归计算每一部分点的Voronoi图,然后再将它们合并。     

汉诺塔非递归算法研究

汉诺塔(Tower of Hanoi)问题是求在三个柱子之间移动圆盘的方法,它是递归程序设计的经典例子,已经证明其时间复杂度下限是O(2n),空间复杂度是O(n),实际使用时很容易溢出.给出汉诺塔问题的两个非递归算法:解集递推法和解集树法.解集递推法的时间复杂度和空间复杂度都是O(2n),该算法空间复杂度很大,无法实际使用,提出该算法的目的是为了引出解集树法.解集树法可以计算出指定的任意一步移动方法,时间复杂度和空间复杂度分别是O(n*2n)和O(1).并证明了汉诺塔问题的空间复杂度下限是O(1).