| 可重构造网孔机器上简单多边形三角剖分的常数时间算法 |
| |
| 引用本文： | 万颖瑜,陈国良,许胤龙. 可重构造网孔机器上简单多边形三角剖分的常数时间算法[J]. 计算机学报, 2002, 25(1): 93-99 |
| |
| 作者姓名： | 万颖瑜 陈国良 许胤龙 |
| |
| 作者单位： | 中国科学技术大学计算机科学与技术系,合肥,230027,国家高性能计算中心,合肥,230027;中国科学技术大学计算机科学与技术系,合肥,230027,国家高性能计算中心,合肥,230027;中国科学技术大学计算机科学与技术系,合肥,230027,国家高性能计算中心,合肥,230027 |
| |
| 摘 要： | 简单多边形的三角剖分是计算几何的基本问题之一 ,在计算机图形学、地理信息系统及有限元方法等领域有许多重要的应用 .可重构造网孔机器是近几年出现的一种新的并行计算模型 ,由于其特有的灵活性 ,已经有很多领域的基本问题在这种模型上得到了研究 .该文在这种结构上考虑了简单多边形的三角剖分问题 :提出了一个将简单多边形分解为特殊单调多边形的算法 ,并在规模为 n× n的可重构造网孔机器上实现了常数时间分解单调多边形为特殊单调多边形的并行算法 ,基于这个算法得到了一个 n× n的机器上常数时间三角剖分单调多边形的算法 ;将这些算法稍加推广 ,并使用稍多的处理器 ,得到了一个在规模为 n× n1 ε(0 <ε<1为常数 )的可重构造网孔机器上三角剖分简单多边形的常数时间算法 .就目前了解到的情况而言 ,这分别是第一个在常数时间三角剖分单调多边形和简单多边形的并行算法
|
| 关 键 词： | 三角剖分 简单多边形 单调多边形 计算几何 可重构造网孔 并行算法 |
| 修稿时间： | 2000-11-13 |
Constant Time Algorithms for Triangulation of Simple Polygons on Reconfigurable Mesh |
| |
| WAN Ying Yu CHEN Guo Liang XU Yin Long. Constant Time Algorithms for Triangulation of Simple Polygons on Reconfigurable Mesh[J]. Chinese Journal of Computers, 2002, 25(1): 93-99 |
| |
| Authors: | WAN Ying Yu CHEN Guo Liang XU Yin Long |
| |
| Abstract: | |
| |
| Keywords: | triangulation simple polygon monotone polygon computational geometry reconfigurable mesh parallel algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
