可重构造网孔机器上简单多边形三角剖分的常数时间算法

• 作者: 万颖瑜 许胤龙 陈国良
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 三角剖分 简单多边形 单调多边形 计算几何 可重构造网孔 并行算法
• 年，卷（期）: 2002,（1）
• 所属期刊栏目: 学术通信
• 页码范围: 93-99
• 页数: 7页
• 分类号: TP301
• 字数: 7290字
• 语种: 中文
• DOI: 10.3321/j.issn:0254-4164.2002.01.014

摘要

简单多边形的三角剖分是计算几何的基本问题之一,在计算机图形学、地理信息系统及有限元方法等领域有许多重要的应用.可重构造网孔机器是近几年出现的一种新的并行计算模型,由于其特有的灵活性,已经有很多领域的基本问题在这种模型上得到了研究. 该文在这种结构上考虑了简单多边形的三角剖分问题:提出了一个将简单多边形分解为特殊单调多边形的算法,并在规模为n×n的可重构造网孔机器上实现了常数时间分解单调多边形为特殊单调多边形的并行算法,基于这个算法得到了一个n×n的机器上常数时间三角剖分单调多边形的算法;将这些算法稍加推广,并使用稍多的处理器,得到了一个在规模为n×n1+ε(0<ε<1为常数)的可重构造网孔机器上三角剖分简单多边形的常数时间算法.就目前了解到的情况而言,这分别是第一个在常数时间三角剖分单调多边形和简单多边形的并行算法.