检索结果-内蒙古大学图书馆

作者：刘颖大连海事大学

学位级别：硕士

Euclidean最短路径(ESP)问题是计算几何领域的经典问题。本文针对LR可视多边形中ESP问题的求解算法研究,设计出一个简单、可行的求解算法,为解决一些实际应用问题(如巡视员问题、机器人运动规划等)提供技术支持。因此,针对本问题的研究... 详细信息

Euclidean最短路径(ESP)问题是计算几何领域的经典问题。本文针对LR可视多边形中ESP问题的求解算法研究,设计出一个简单、可行的求解算法,为解决一些实际应用问题(如巡视员问题、机器人运动规划等)提供技术支持。因此,针对本问题的研究,不仅具有重要的理论意义,而且具有较大的实际应用价值。本文针对LR可视多边形P中的ESP问题进行研究,求解从起点s到达终点t的,且完全包含在P内的最短路径。为求解该问题,本文首先论述了与求解ESP问题相关的计算几何领域的基础知识与算法,并通过分析LR可视多边形的性质以及与最短路径的相互关系,给出了基于凸面路径求解最短路径的算法思路。以此为基础,提出了一个以R链为基准链构造右凸面路径,并通过分析L链上的凹顶点与右凸面路径的位置关系,确定L链上属于最短路径SP(s,t)的凹顶点的最短路径求解算法,编程实现所提出的算法并构造测试数据验证了算法的有效性。实验结果表明,本文提出的算法是有效的,能够针对LR可视多边形中可能的ESP问题,求出从给定起点s到达终点t的满足要求的最短路径。

关键词：计算几何 LR可视多边形 ESP问题凸面路径

来源：评论

学校读者我要写书评

暂无评论

保护私有信息的两多边形相交面积计算

引用

计算机工程与应用 2014年第9期50卷 37-40页

作者：傅天裕罗永龙郭良敏孙玲玲安徽师范大学数学计算机科学学院安徽芜湖241003 安徽师范大学网络与信息安全工程技术研究中心安徽芜湖241003

保护私有信息的计算几何是一类特殊的安全多方计算问题,在军事、商业等领域具有重要的应用前景。在半诚实模型下,利用点线叉积协议设计一个保护私有信息的点包含于多边形判定协议;基于该协议,提出保护私有信息的两多边形相交面积计算协... 详细信息

保护私有信息的计算几何是一类特殊的安全多方计算问题,在军事、商业等领域具有重要的应用前景。在半诚实模型下,利用点线叉积协议设计一个保护私有信息的点包含于多边形判定协议;基于该协议,提出保护私有信息的两多边形相交面积计算协议;分析和证明上述协议的正确性、安全性和复杂性。

关键词：安全多方计算计算几何点包含相交面积

来源：评论

学校读者我要写书评

暂无评论

平面上可相交圆序列的最优遍历算法研究

平面上可相交圆序列的最优遍历算法研究

引用

作者：丁月鹏大连海事大学

学位级别：硕士

本文针对平面上可相交圆序列的最优遍历问题进行研究,目标是研究并设计一个遍历算法,使其能够找到一条从起始点出发,到终止点结束,并依次遍历每个圆的最短遍历路径。该问题是经典的旅行商问题的一种变形,属于计算几何领域的一个理论问题... 详细信息

本文针对平面上可相交圆序列的最优遍历问题进行研究,目标是研究并设计一个遍历算法,使其能够找到一条从起始点出发,到终止点结束,并依次遍历每个圆的最短遍历路径。该问题是经典的旅行商问题的一种变形,属于计算几何领域的一个理论问题,因此,具有较高的理论价值。同时,很多实际问题的抽象模型也与该问题相似,如路线规划、分层制造、无线传感器网络传输等问题,因此研究该问题也具有很高的实际应用价值。在算法设计部分,本文首先论述几何物体遍历相关的一些基础知识和基本算法,并在此基础上,分析了现有相关遍历问题的研究成果,如平面上线段、凸多边形序列等遍历问题的最新成果,结合圆序列的局部几何特性,设计了一种利用相邻圆之间的切线进行必要的区域划分的方法。利用这种区域划分方法,将局部圆序列划分出不同的区域,并以此来确定局部最短路径点求解方案。在确定局部最短路径的求解方案之后,利用局部最优进行迭代计算,并构造出全局最优的遍历路径。在整个求解过程中,本文采用分而治之的思想,将圆序列整体分段,然后针对每个小段中点与圆的位置关系,分析遍历圆时可能出现的局部最优的访问类型,并根据小段中点与圆不同的位置关系设计出了合适的区域划分方案。最后,对不同的局部最优访问类型,分别给出了局部最优遍历路径的计算方法。本文详细证明了可相交圆序列最短遍历路径的存在性和唯一性,并借鉴线段序列遍历的算法思想,如动态规划,设计出了时间复杂度不超过O(n2)的算法。在实验部分,本文通过编程实现了算法,利用大量测试数据的实验结果来验证算法的有效性。通过大量实践论证,本文提出的可相交圆序列遍历算法,是目前求解平面上圆序列遍历问题的有效算法。

关键词：计算几何最短遍历路径圆序列路径点

来源：评论

学校读者我要写书评

暂无评论

自适应二分的并行Delaunay三角网生长算法

引用

信阳师范学院学报（自然科学版） 2022年第4期35卷 656-663页

作者：尤磊晏成名宋新宇信阳师范学院计算机与信息技术学院河南信阳464000 信阳师范学院河南省物联网与智能安防工程研究中心河南信阳464000 信阳师范学院数学与统计学院河南信阳464000

为提升平面点集Delaunay三角网的构建效率,提出了一种点集自适应二分与子集并行构建Delaunay三角网的算法。首先根据点集中点的分布,构建点集二分的引导线;接着采用优先点为中心的Delaunay三角网生成算法沿着引导线构建三角形,并根据点... 详细信息

为提升平面点集Delaunay三角网的构建效率,提出了一种点集自适应二分与子集并行构建Delaunay三角网的算法。首先根据点集中点的分布,构建点集二分的引导线;接着采用优先点为中心的Delaunay三角网生成算法沿着引导线构建三角形,并根据点与三角形的位置关系将点集划分为2个子集,再分别对各个子集并行二分,直至每个子集中点的数量小于分割阈值;然后并行构建子集的Delaunay三角网;最后将点集二分时生成的三角形与子网构建的三角网直接合并,得到全局的Delaunay三角网。不同点集规模与不同分割阈值的实验表明:所提算法可有效提升Delaunay三角网的构建效率;分割阈值为900时,所提算法的构网时间随点集规模趋近于线性增长;点集规模为3万时,不同分割阈值下的平均提升效率为66.11%。所提算法充分发挥了Delaunay三角网的局部性与全局性的优点,确保了构建的每一个三角形都是最终的三角形,从而有效提升了构网效率,也为构建点集的局部Delaunay三角网提供一个可行方案。

关键词：计算几何 Delaunay三角网并行计算优先点 OpenMP

来源：评论

学校读者我要写书评

暂无评论

未知区域中目标搜索的online算法研究

未知区域中目标搜索的online算法研究

引用

作者：魏琦大连海事大学

学位级别：博士

online搜索问题是计算几何学、机器人学、算法学中的热点研究问题,它不仅涉及动态搜索、最优路径规划、算法设计与分析等基础理论问题,还在危险区域撤离、机器人目标搜索、未知区域探索等领域有着广泛的应用。研究针对这类问题的简洁、... 详细信息

online搜索问题是计算几何学、机器人学、算法学中的热点研究问题,它不仅涉及动态搜索、最优路径规划、算法设计与分析等基础理论问题,还在危险区域撤离、机器人目标搜索、未知区域探索等领域有着广泛的应用。研究针对这类问题的简洁、高效算法,不仅具有理论意义,而且还具有很大的实际应用价值。尽管近年来online搜索问题的研究取得了一些优秀的成果,但仍有很多经典的开放性问题没有解决,且一些成果还存在着效率没达到最优、限制条件多等问题。在此背景下,本文针对online搜索中三个具体问题,展开深入研究。首先是信息不完备的危险区域撤离问题。针对这一问题,本文分单人撤离和多人撤离两种情况讨论。在单人撤离情况中,提出了竞争比为13.812的对数螺线算法,且通过给出匹配的竞争比下界,证明了该算法是最优的单调周期性算法。同时,将对数螺线单调周期性的性质应用在网格模型中,提出了竞争比为21的螺旋撤离算法。在多人撤离情况中,提出了一个新的等角撤离算法EES,给出了竞争比计算通式,并在分析算法竞争比的基础上对分组方式做了进一步的优化研究。其次,是最小感知能力机器人街道搜索问题。针对这一问题,本文提出了竞争比为9的最优online搜索算法。该算法不仅在效率上有所提升,将竞争比从原有算法的11降低到现在的9,还去掉了机器人需要携带位置标记装置及使用数据结构S-GNT的限制。最后,是基于可视性的未知多边形探索问题。针对这一问题,本文提出了一个竞争比为6.7的online探索算法。该算法通过将(?)倍的offline巡视员路径近似算法online化,递归地探索多边形中的两类凹顶点,及合理地使用结构角壳,将竞争比从原有算法的26.5降低到6.7,大幅提升了探索效率。本文提出的这些算法是相应问题到目前为止的最优解决方案。它们不仅解决了online搜索领域中的一些理论问题,还在危险区域撤离、机器人搜索、探索等领域中有着广泛的应用前景。

关键词：计算几何目标搜索 online算法机器人竞争比

来源：评论

学校读者我要写书评

暂无评论

一种基于点集自适应分组构建Voronoi图的并行算法

引用

图学学报 2012年第6期33卷 7-13页

作者：王结臣蒲英霞崔璨陈刚马劲松江苏省地理信息技术重点实验室江苏南京210093 南京大学地理信息科学系江苏南京210093

论文提出一种基于点集自适应分组构建Voronoi图的并行算法,其基本思路是采用二叉树分裂的方法将平面点集进行自适应分组,将各分组内的点集独立生成Voronoi图,称为Voronoi子图;提取所有分组内位于四边的边界点,对边界点集构建Voronoi图,... 详细信息

论文提出一种基于点集自适应分组构建Voronoi图的并行算法,其基本思路是采用二叉树分裂的方法将平面点集进行自适应分组,将各分组内的点集独立生成Voronoi图,称为Voronoi子图;提取所有分组内位于四边的边界点,对边界点集构建Voronoi图,称为边界点Voronoi图;最后,针对每个边界点,提取其位于Voronoi子图和边界点Voronoi图内所对应的两个多边形,进行Voronoi多边形的合并,最终实现子网的合并。考虑到算法耗时主要在分组点集的Voronoi图生成,而各分组的算法实现不受其他分组影响,采用并行计算技术加速分组点集的Voronoi图生成。理论分析和测试表明,该算法是一个效率较高的Voronoi图生成并行算法。

关键词： Voronoi图并行算法自适应分组计算几何

来源：评论

学校读者我要写书评

暂无评论

改进的二维点集凸包快速求取方法

引用

武汉理工大学学报 2005年第10期27卷 81-83,92页

作者：余翔宇孙洪余志雄武汉大学电子信息学院武汉430072

凸包问题是计算几何的基本问题,分为平面点集凸包和多边形凸包2类。对传统点集快速凸包算法进行改进,通过找到点集中8个方向的极值点来准确地确定凸包上的部分顶点,得到凸包的粗略逼近,接着在逼近结果上进行遍历,使用链表或栈这样的数... 详细信息

凸包问题是计算几何的基本问题,分为平面点集凸包和多边形凸包2类。对传统点集快速凸包算法进行改进,通过找到点集中8个方向的极值点来准确地确定凸包上的部分顶点,得到凸包的粗略逼近,接着在逼近结果上进行遍历,使用链表或栈这样的数据结构,找到逼近结果中连续2个顶点之间的漏检点,从而得到完整的凸包。整个过程达到复杂度下限,且在通常情况下接近线性时间。该方法已经有效地应用于基于控制点的图像配准中。

关键词：凸包平面点集计算几何链表栈

来源：评论

学校读者我要写书评

暂无评论

VisualC^(++)实现单调多边形三角剖分

引用

大连海事大学学报 2002年第2期28卷 106-108页

作者：薛伟莲王志强辽宁师范大学信息管理系辽宁大连116029 大连海事大学数理系辽宁大连116026

多边形三角剖分是计算几何的一个几何基元 .它可以简化问题规模 ,在计算机图形学、模式识别和地理数据库方面有重要应用 .低时间复杂度是设计多边形三角剖分算法的基本要求 .针对现有单调多边形算法的不足 ,提出一个复杂度为O(N)的算法 ... 详细信息

多边形三角剖分是计算几何的一个几何基元 .它可以简化问题规模 ,在计算机图形学、模式识别和地理数据库方面有重要应用 .低时间复杂度是设计多边形三角剖分算法的基本要求 .针对现有单调多边形算法的不足 ,提出一个复杂度为O(N)的算法 ,并在VisualC+ +

关键词： VisualC^++ 计算机语言多边形单调多边形三角剖分计算几何计算图形学

来源：评论

学校读者我要写书评

暂无评论

二维凸壳算法在合成金属设计中的应用

引用

计算机应用与软件 2007年第12期24卷 142-144页

作者：邓安远李伟九江学院信息科学与技术学院江西九江332005

计算几何主要研究解决几何问题的算法。计算几何在图形学、机器人技术、超大规模集成电路设计等诸多领域有着十分重要的应用。凸壳[1]是计算几何中最普遍、最基本的一种结构,凸壳不仅自身有许多特性,而且它还是构造其他几何形体的有效... 详细信息

计算几何主要研究解决几何问题的算法。计算几何在图形学、机器人技术、超大规模集成电路设计等诸多领域有着十分重要的应用。凸壳[1]是计算几何中最普遍、最基本的一种结构,凸壳不仅自身有许多特性,而且它还是构造其他几何形体的有效工具。在实际的应用中,许多实际问题可以通过构造凸壳转化为凸壳问题加以解决。详细地介绍了凸壳的基本概念和生成在一定点集上的凸壳的算法以及应用凸壳的基本原理来解决现实生活中的一些问题。

关键词：凸亮计算几何金属合成

来源：评论

学校读者我要写书评

暂无评论

基于动态分区技术的Ad hoc混合式网络路由协议

引用

计算机工程与设计 2007年第20期28卷 4923-4926页

作者：张尚悦贾传荧伞戈锐王书晓大连海事大学航海动态仿真与控制实验室辽宁大连116026 大连舰艇学院航海系辽宁大连116018

在分析目前Ad hoc网络中常见的4种路由协议基础上,首次提出了应用计算几何中最小覆盖问题算法,并借鉴了GSM、CDMA移动通讯中的蜂窝位置管理技术,设计了一种基于动态分区的Ad hoc混合式网络路由协议:将Ad hoc网络中的各个节点进行动态地... 详细信息

在分析目前Ad hoc网络中常见的4种路由协议基础上,首次提出了应用计算几何中最小覆盖问题算法,并借鉴了GSM、CDMA移动通讯中的蜂窝位置管理技术,设计了一种基于动态分区的Ad hoc混合式网络路由协议:将Ad hoc网络中的各个节点进行动态地划分为若干个"移动蜂窝"。在动态分区范围内使用先验式路由协议,缩小路由控制消息传播的范围。在动态分区间,通过查找每一个节点的归属分区寄存器,在动态分区间发现路由。实践证明,该混合式网络路由协议既减少路由协议的开销,也改善了时延特性。

关键词：计算几何动态分区混合式网络路由协议

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：