ON SIMILARITY OF POLYNOMIAL CONFIGURATIONS

被引：0

作者：

RAO, NSV

LUO, C

机构：

[1] Department of Computer Science, Old Dominion University, Norfolk

来源：

INFORMATION PROCESSING LETTERS | 1993年 / 47卷 / 05期

关键词：

AFFINE TRANSFORMATIONS; POLYNOMIAL CONFIGURATIONS; FAST FOURIER TRANSFORMS; ALGORITHMS; COMPUTATIONAL COMPLEXITY;

D O I：

10.1016/0020-0190(93)90132-S

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The problem of checking the equivalence of two sets of polynomial curves (in a plane), each set of total degree n, under the affine transformations of translation, rotation, scaling and mirror reflection is studied. An optimal THETA(n log n) time algorithm for this problem is presented. This algorithm is based on efficient computation of Bezier polygons by using some polynomial manipulations that employ FFT methods.

引用

页码：231 / 236

页数：6

共 16 条

[1]

Aho A.V., 1983, DESIGN ANAL COMPUTER

[2]

Akl S. G., 1989, DESIGN ANAL PARALLEL

[3]

AKL SG, 1978, INFORM PROCESS LETT, V3, P127

[4] PARALLEL CONSTRUCTION OF A SUFFIX TREE WITH APPLICATIONS [J].

APOSTOLICO, A ;

ILIOPOULOS, C ;

LANDAU, GM ;

SCHIEBER, B ;

VISHKIN, U .

ALGORITHMICA, 1988, 3 (03) :347-365

[5] AN OPTIMAL ALGORITHM FOR GEOMETRICAL CONGRUENCE [J].

ATKINSON, MD .

JOURNAL OF ALGORITHMS, 1987, 8 (02) :159-172

[6]

BOREDDY J, 1989, INFORM PROCESS LETT, V1, P23

[7] POLYGON SIMILARITY [J].

BYKAT, A .

INFORMATION PROCESSING LETTERS, 1979, 9 (01) :23-25

[8] PARALLEL MERGE SORT [J].

COLE, R .

SIAM JOURNAL ON COMPUTING, 1988, 17 (04) :770-785

[9]

Farin G., 2002, MORGAN KAUFMANN SERI, Vfifth

[10]

Galil Z., 1988, Journal of Complexity, V4, P33, DOI 10.1016/0885-064X(88)90008-8

← 1 2 →