On similarity of polynomial configurations

Nageswara S.V. Rao; Ching Luo

doi:10.1016/0020-0190(93)90132-S

On similarity of polynomial configurations

Research output: Contribution to journal › Article › peer-review

Abstract

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 Θ(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.

Original language	English
Pages (from-to)	231-236
Number of pages	6
Journal	Information Processing Letters
Volume	47
Issue number	5
DOIs	https://doi.org/10.1016/0020-0190(93)90132-S
State	Published - Oct 8 1993
Externally published	Yes

Keywords

Affine transformations
algorithms
computational complexity
fast Fourier transforms
polynomial configurations

Access to Document

10.1016/0020-0190(93)90132-S

Cite this

@article{275de42cec5749029249c853ae8c1303,

title = "On similarity of polynomial configurations",

abstract = "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 Θ(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.",

keywords = "Affine transformations, algorithms, computational complexity, fast Fourier transforms, polynomial configurations",

author = "Rao, {Nageswara S.V.} and Ching Luo",

year = "1993",

month = oct,

day = "8",

doi = "10.1016/0020-0190(93)90132-S",

language = "English",

volume = "47",

pages = "231--236",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "5",

}

TY - JOUR

T1 - On similarity of polynomial configurations

AU - Rao, Nageswara S.V.

AU - Luo, Ching

PY - 1993/10/8

Y1 - 1993/10/8

N2 - 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 Θ(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.

AB - 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 Θ(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.

KW - Affine transformations

KW - algorithms

KW - computational complexity

KW - fast Fourier transforms

KW - polynomial configurations

UR - http://www.scopus.com/inward/record.url?scp=0027912267&partnerID=8YFLogxK

U2 - 10.1016/0020-0190(93)90132-S

DO - 10.1016/0020-0190(93)90132-S

M3 - Article

AN - SCOPUS:0027912267

SN - 0020-0190

VL - 47

SP - 231

EP - 236

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

On similarity of polynomial configurations

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this