计算几何是一门新兴的学科,它在计算机图形学、模式识别和地理数据库等领域有着广泛的应用.一维可重构流水线总线并行机是一种基于光通信技术的并行计算模型,它具有以往模型没有的很多优点,使得在它上面可以设计出一些非常快速又更易于实现的并行算法,所以在该模型上研究计算几何算法具有重要的理论意义和实用价值.该文研究了LARPBS(a Linear Array with a Reconfigurable Pipelined Bus System)模型上计算几何中平面点集的凸壳、距离变换和单调多边形的三角剖分等三个基本问题,分别提出了相应的并行算法.该文的主要内容、贡献和创新包括:(1)LARPBS上平面点集的凸壳算法提出分离的概念,并指出:两个分离凸壳间的合并可通过并行计算点到凸壳的切线来完成,设计了两分离凸壳间的合并算法,该算法具有直观、简明和高效的优点.基于分治的思想,利用该算法,设计出凸壳算法.(2)LARPBS上任意维二值图像的距离变换算法采用转换的思想,使高维图像的距离变换问题简化为求解若干个低维图像的距离变换子问题,并设计了转换算法.利用已有的LARPBS上二维图像的距离变换算法,得到了任意维图像的距离变换算法.(3)LARPBS上序列的最近较小(ANSV)算法提出匹配分割的概念,使问题简化为合并有序序列和按序分布数据.通过灵活拆分总线和合并子总线的方法动态重构光总线系统,并巧妙利用光总线的消息播送技术,设计了数据移动算法.结合已有的合并有序序列的结论,提出了ANSV算法.(4)LARPBS上单调多边形的三角剖分算法将已有的算法思想在LARPBS上实现,证明了该算法的执行时间主要取决于确定顶点的可视点一这步操作所需的时间.然后将该操作归约为求解ANSV问题,利用ANSV算法,提出了一个单调多边形三角剖分算法.
随着互联网的迅速发展，促进了信息处理和信息交互的技术的研究与应用，其中研究应用的热点之一便是在计算机网络环境下的合作协同计算。合作协同计算不仅发生在合作者之间的，甚至在竞争对手之间也需要这样的计算。合作协同计算需要各个参与方提供自己拥有的秘密信息作为计算的输入，然后通过事先协商好的计算规则进行交互执行，最后各个参与方获得其相应的输出结果。由于，在公开的网络环境下，参与方都是互不信任的，甚至可能出现恶意敌手的情况，他们不遵守协议规则，企图破坏、篡改或窃取其他参与方的秘密数据信息的情况。为了保护诚实、合法参与方的利益以及他们的秘密信息的安全，确保协议能正确执行以及参与方的公平性等，本文对这样的合作协同计算的安全多方计算协议进行了研究，同时提出了保护隐私的计算几何位置关系判定的若干协议。\n 20世纪80年代，由A C Yao首次提出百万富翁协议，顺利解决了秘密比较两个整数的大小的问题，这是第一个被公认的安全多方计算问题的成功应用。其后，Goldreich等人进行了系统地研究和探讨，对安全多方计算提出了更加全面的定义和描述，并构建了系统化的理论基础。如今，安全多方计算已成为了国际密码学界的研究热点之一，拥有着众多研究学者和丰硕的研究成果，其研究应用领域涵盖了：科学计算、电子拍卖、电子投票、具有保护隐私的密钥管理、数据挖掘、信息检索等。同时，保护隐私的计算几何问题是安全多方计算的一个重要分支，本文对此课题进行了重点的研究与探讨。保护隐私的计算几何的研究对现代网络商务飞速发展的当下有着重要的战略意义：对国家的电子商务、在线政府服务、金融交易以及军事合作等领域的安全健康地发展有着重大的实践意义。\n 本文首先对安全多方计算的背景知识、研究意义、发展与现状、理论定义和安全模型进行了总结和概述。其次，针对安全多方计算的组成基础模块、构造子协议、密码算法等进行了探讨和研究，着重对设计协议需要使用到的若干子协议和密码算法进行了引用分析和概述，如不经意传输协议、同态加密算法、点乘协议、保密集合交协议等。对集合交算法进行了深层次的探讨，以及部分的改进。然后，基于上述的理论基础和研究结论，通过比较不同的几何位置判定算法，提出了基于铅垂线算法和不经意传输协议的、保护隐私的几何对象位置关系判定协议。其中，包括有：点与直线、线段与线段、点与多边形、线段与多边形、多边形与多边形的位置关系判定协议；同时，分析了协议在计算和通信代价。最后，重点设计了保护隐私的点与多边形的位置关系判定协议。采用了基于铅垂线算法和不经意传输协议，与以往的协议相比较，新的协议具有更高的通用性，例如：可以适用于任意的多边形情况(包括凹多边形、多边形带孔)，涉及的数据可以拓展到实数域等优势。
暂无评论