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

摘要

计算几何是一门新兴的学科,它在计算机图形学、模式识别和地理数据库等领域有着广泛的应用.一维可重构流水线总线并行机是一种基于光通信技术的并行计算模型,它具有以往模型没有的很多优点,使得在它上面可以设计出一些非常快速又更易于实现的并行算法,所以在该模型上研究计算几何算法具有重要的理论意义和实用价值.该文研究了LARPBS(a Linear Array with a Reconfigurable Pipelined Bus System)模型上计算几何中平面点集的凸壳、距离变换和单调多边形的三角剖分等三个基本问题,分别提出了相应的并行算法.该文的主要内容、贡献和创新包括:(1)LARPBS上平面点集的凸壳算法提出分离的概念,并指出:两个分离凸壳间的合并可通过并行计算点到凸壳的切线来完成,设计了两分离凸壳间的合并算法,该算法具有直观、简明和高效的优点.基于分治的思想,利用该算法,设计出凸壳算法.(2)LARPBS上任意维二值图像的距离变换算法采用转换的思想,使高维图像的距离变换问题简化为求解若干个低维图像的距离变换子问题,并设计了转换算法.利用已有的LARPBS上二维图像的距离变换算法,得到了任意维图像的距离变换算法.(3)LARPBS上序列的最近较小(ANSV)算法提出匹配分割的概念,使问题简化为合并有序序列和按序分布数据.通过灵活拆分总线和合并子总线的方法动态重构光总线系统,并巧妙利用光总线的消息播送技术,设计了数据移动算法.结合已有的合并有序序列的结论,提出了ANSV算法.(4)LARPBS上单调多边形的三角剖分算法将已有的算法思想在LARPBS上实现,证明了该算法的执行时间主要取决于确定顶点的可视点一这步操作所需的时间.然后将该操作归约为求解ANSV问题,利用ANSV算法,提出了一个单调多边形三角剖分算法.

目录

文摘

英文文摘

第1章绪论

1.1研究背景

1.1.1计算几何学

1.1.2计算几何的应用

1.2研究内容及主要成果

1.3论文的组织

第2章模型和研究现状

2.1发展历史

2.2模型定义

2.2.1 LARPBS模型的结构

2.2.2脉冲吻合寻址技术

2.2.3 LARPBS模型上的基本数据操作

2.3研究现状

2.4本章小结

第3章平面点集的凸壳算法

3.1问题定义及研究现状

3.2基本概念

3.3切线算法

3.4凸壳算法

3.4.1合并算法

3.4.2凸壳算法

3.5本章总结

第4章二值图像的距离变换

4.1图象的距离变换

4.2基本概念及性质

4.3转换图的距离变换算法

4.3.1算法的基本原理

4.3.2算法及复杂度分析

4.4任意维的二值图像的距离变换算法

4.4.1算法的基本原理及相关操作

4.4.2算法描述

4.5本章小结

第5章序列的最近较小值问题

5.1序列的最近较小值问题

5.2基本概念及性质

5.3特定序列的ANSV算法

5.3.1算法的基本思想

5.3.2匹配分割算法

5.3.3特定序列的ANSV算法

5.4 ANSV算法

5.5本章小结

第6章多边形的三角剖分算法

6.1多边形的三角剖分

6.2基本概念

6.3并行算法

6.3.1特殊单调多边形的三角剖分算法

6.3.2单调多边形的三角剖分算法

6.4本章小结

第7章总结

7.1本文的工作

7.2进一步的工作

算法索引

插图索引

参考文献

致谢

在读期间参加的项目

在读期间发表和接收的论文