A COST-OPTIMAL PARALLEL ALGORITHM FOR B-SPLINE SURFACE FITTING

被引：4

作者：

CHUNG, KL

LIN, FC

机构：

[1] Department of Computer Science and Information Engineering, National Taiwan University, Taipei

来源：

CVGIP-GRAPHICAL MODELS AND IMAGE PROCESSING | 1991年 / 53卷 / 06期

关键词：

D O I：

10.1016/1049-9652(91)90010-H

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We show how to transform the B-spline surface fitting problem into suffix computations of continued fractions. Then a parallel substitution scheme is used to compute the suffix values on a newly proposed mesh-of-unshuffle network. The derived parallel algorithm allows the surface interpolation at m × n points to be solved in O(log m log n) time using Θ( mn (log m log n)) processors. The algorithm is cost-optimal in the sense that number of processors times execution time is minimized. The problem can be even more quickly solved in O(log m + log n) time if Θ(mn) processors are used in the network. © 1991.

引用

页码：601 / 605

页数：5

共 9 条

[1] BARNHILL RE, 1974, COMPUTER AIDED GEOME
[2] DETERMINING A SET OF B-SPLINE CONTROL VERTICES TO GENERATE AN INTERPOLATING SURFACE
BARSKY, BA
GREENBERG, DP
[J]. COMPUTER GRAPHICS AND IMAGE PROCESSING, 1980, 14 (03): : 203 - 226
[3] CHENG F, 1989, ACM T GRAPHIC, V8, P41, DOI 10.1145/49155.214377
[4] CHUNG KL, IN PRESS J PARALLEL
[5] de Boor C., 1978, PRACTICAL GUIDE SPLI
[6] Faux ID, 1979, COMPUTATIONAL GEOMET
[7] SOLVING TRIDIAGONAL SYSTEMS ON ENSEMBLE ARCHITECTURES
JOHNSSON, SL
[J]. SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING, 1987, 8 (03): : 354 - 392
[8] PARALLEL SORTING WITH SERIAL MEMORIES
OWENS, RM
JA, JJ
[J]. IEEE TRANSACTIONS ON COMPUTERS, 1985, 34 (04) : 379 - 383
[9] Stone H. S., 1975, ACM Transactions on Mathematical Software, V1, P289, DOI 10.1145/355656.355657

← 1 →