一维可重构流水线总线并行机上计算几何算法的设计

《一维可重构流水线总线并行机上计算几何算法的设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中田许擘技术大学硕士学位论文一堆可重构流水残总线并行机上计算几何算法的设计LARPBSTheconceptionofmatchingseparationispresented，thustheproblemofAllNearestSmallerValues(ANSV)issimplifiedtomergingtwosortedsequencesanddistributingdatainorder．Furthermore，analgorithmfordatadistributiononLARPBSisprese

2、nted，basedondelicateutilizationoftwoschemes，namely,dynamicreconfigurationofopticalbussysteminasplit-mergeapproach，andthemessage-passingtechnique．Combiningouralgorithmwithexistingconclusionsaboutsoaed·sequencemerging，WeproposedanANSValgorithm．．(4)Atriangula

3、tionalgorithmformonotonepolygononLARPBSWeimplementapreviousknownalgorithmonLARPBS，andprovethatitsrunningtimeliesonthecomputationofthevisiblepointofavertex．ThenwereducethiscomputationsteptoANSVproblem,and，utilizingavailableANSValgorithms，presentalloriginalt

4、riangulationalgorithmformonotonepolygons．KeyWords：computationalgeometry,reconfigurablepipelinedbussystem，convexhull，distancetransformation，monotonepolygon，triangulation，parallelalgorithms．ⅡI中函科学技术太学硕士学位论文一维可重构流水残总线并行机上计算几何算法的设计第1章绪论本章摘要：计算几何是理论计算机科学领域中一个新的

5、具有生命力的子领域。本章先阐述了计算几何中的一些基本问题；然后提出了本文的研究内容，并综述了丈中取得的研究成果：最后给出论文的章节安排．1．1研究背景计算几何学是研究几何外形信息的计算机表示、分析和综合的新兴边缘学科。由于大量的应用领域提供了特有的几何问题，对于这些问题必须建立有效的算法，这就是孕育计算机几何这门学问的基础。下面介绍与计算几何相关的一些概念及应用。1．1．1计算几何学1975年，Shamos(沙莫斯)和Hoey(霍伊)利用计算机有效地计算平面点集的Voronoi图，并发表了一篇著名论文，从此

6、计算几何诞生了。计算几何是几何学的一个扩展，随着计算机技术的飞速发展，它研究的对象已经远超出了几何学的研究范围。它研究的几何问题往往包括了大量的几何对象，比如点或线的集合。它是理论计算机领域中一个新的极有生命力的子领域。计算几何研究的典型问题由几何基元(geometricprimitives)、查找、优化等问题类组成。首先，几何基元包括t)计算点集的凸壳和Voronoi图，抖l维空间中点集s的下凸壳在d维空间中的投影，恰是s在d维空间中投影点的Delaunay三角剖分，然后由Delaunay三角剖分很容易得

7、到Voronoi图：2)计算若干几何体的交点，二维中的典型相交问题是：给定平面上H条直线段，确定所有的相交线对。三维中的相交问题一般考虑两个凸多面体的交以及两个多面体的交：3)将一个复杂的几何体划分成若干个简单几何体。划分问题是多边形三角剖分问题的推广，它要求把几何体划分成尽量少的凸部分，并且各凸部分最小角最大化。其次，几何查找或者称几何检索，它是指在属性相同的一批几何对象(比如点、直线段、圆、多边形、多面体等)中定位某个指定的几何对象。或者在某个特定的域中寻找该域所包含的具有某种属性的所有几何对象。即几何

8、查找包括两类主要的问题；1)几何体定位问题；2)范围查找问题。另外还包括可视化问题，中田抖学技术大擘硕士学位论文一堆可重构漶水线总蠼并行机上计算几竹算法的设计如：给定平面上一个顶点的简单多边形P，出点q向任一方向引射线f，确定，与P相交的第一条边。再次，几何优化包括1)参数查找，如：给定一个点集量定位一个或几个新的点，使得与至S点距离有关的某些目标函数最小化(覆盖问题)或者最大化(间隙问题)；2)线性规划。此外，