Optimal Hierarchies for Quadrilateral Surfaces

Kuo Liang Chung, Wen Ming Yan, Jung Gen Wu

Research output: Contribution to journalArticle

Abstract

Multiresolution representation of quadrilateral surface approximation (MRQSA) is a useful representation for progressive graphics transmission in networks. Based on two requirements: (1) minimum mean square error and (2) fixed reduction ratio between levels, this paper first transforms the MRQSA problem into the problem of solving a sequence of near-Toeplitz tridiagonal linear systems. Employing the matrix perturbation technique, the MRQSA problem can be solved using about 24mn floating-point operations, i.e. linear time, if we are given a polygonal surface with (2m-1)×(2n-1) points. A numerical stability analysis is also given. To the best of our knowledge, this is the first time that such a linear algebra approach has been used for solving the MRQSA problem. Some experimental results are carried out to demonstrate the applicability of the proposed method.

Original languageEnglish
Pages (from-to)283-300
Number of pages18
JournalJournal of Mathematical Modelling and Algorithms
Volume1
Issue number4
DOIs
Publication statusPublished - 2002 Dec 1

Fingerprint

Surface Approximation
Multiresolution
Approximation Problem
Matrix Perturbation
Tridiagonal Systems
Perturbation Technique
Minimum Mean Square Error
Otto Toeplitz
Floating point
Numerical Stability
Linear algebra
Perturbation techniques
Convergence of numerical methods
Linear Time
Numerical Analysis
Stability Analysis
Mean square error
Linear Systems
Linear systems
Transform

Keywords

  • multiresolution representation
  • near-Toeplitz tridiagonal systems
  • quadrilateral surface
  • stability analysis

ASJC Scopus subject areas

  • Modelling and Simulation
  • Applied Mathematics

Cite this

Optimal Hierarchies for Quadrilateral Surfaces. / Chung, Kuo Liang; Yan, Wen Ming; Wu, Jung Gen.

In: Journal of Mathematical Modelling and Algorithms, Vol. 1, No. 4, 01.12.2002, p. 283-300.

Research output: Contribution to journalArticle

Chung, Kuo Liang ; Yan, Wen Ming ; Wu, Jung Gen. / Optimal Hierarchies for Quadrilateral Surfaces. In: Journal of Mathematical Modelling and Algorithms. 2002 ; Vol. 1, No. 4. pp. 283-300.
@article{fa31b7024460478da6777010ae4d7ac0,
title = "Optimal Hierarchies for Quadrilateral Surfaces",
abstract = "Multiresolution representation of quadrilateral surface approximation (MRQSA) is a useful representation for progressive graphics transmission in networks. Based on two requirements: (1) minimum mean square error and (2) fixed reduction ratio between levels, this paper first transforms the MRQSA problem into the problem of solving a sequence of near-Toeplitz tridiagonal linear systems. Employing the matrix perturbation technique, the MRQSA problem can be solved using about 24mn floating-point operations, i.e. linear time, if we are given a polygonal surface with (2m-1)×(2n-1) points. A numerical stability analysis is also given. To the best of our knowledge, this is the first time that such a linear algebra approach has been used for solving the MRQSA problem. Some experimental results are carried out to demonstrate the applicability of the proposed method.",
keywords = "multiresolution representation, near-Toeplitz tridiagonal systems, quadrilateral surface, stability analysis",
author = "Chung, {Kuo Liang} and Yan, {Wen Ming} and Wu, {Jung Gen}",
year = "2002",
month = "12",
day = "1",
doi = "10.1023/A:1021603330228",
language = "English",
volume = "1",
pages = "283--300",
journal = "Journal of Mathematical Modelling and Algorithms",
issn = "1570-1166",
publisher = "Springer Netherlands",
number = "4",

}

TY - JOUR

T1 - Optimal Hierarchies for Quadrilateral Surfaces

AU - Chung, Kuo Liang

AU - Yan, Wen Ming

AU - Wu, Jung Gen

PY - 2002/12/1

Y1 - 2002/12/1

N2 - Multiresolution representation of quadrilateral surface approximation (MRQSA) is a useful representation for progressive graphics transmission in networks. Based on two requirements: (1) minimum mean square error and (2) fixed reduction ratio between levels, this paper first transforms the MRQSA problem into the problem of solving a sequence of near-Toeplitz tridiagonal linear systems. Employing the matrix perturbation technique, the MRQSA problem can be solved using about 24mn floating-point operations, i.e. linear time, if we are given a polygonal surface with (2m-1)×(2n-1) points. A numerical stability analysis is also given. To the best of our knowledge, this is the first time that such a linear algebra approach has been used for solving the MRQSA problem. Some experimental results are carried out to demonstrate the applicability of the proposed method.

AB - Multiresolution representation of quadrilateral surface approximation (MRQSA) is a useful representation for progressive graphics transmission in networks. Based on two requirements: (1) minimum mean square error and (2) fixed reduction ratio between levels, this paper first transforms the MRQSA problem into the problem of solving a sequence of near-Toeplitz tridiagonal linear systems. Employing the matrix perturbation technique, the MRQSA problem can be solved using about 24mn floating-point operations, i.e. linear time, if we are given a polygonal surface with (2m-1)×(2n-1) points. A numerical stability analysis is also given. To the best of our knowledge, this is the first time that such a linear algebra approach has been used for solving the MRQSA problem. Some experimental results are carried out to demonstrate the applicability of the proposed method.

KW - multiresolution representation

KW - near-Toeplitz tridiagonal systems

KW - quadrilateral surface

KW - stability analysis

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

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

U2 - 10.1023/A:1021603330228

DO - 10.1023/A:1021603330228

M3 - Article

AN - SCOPUS:84888606481

VL - 1

SP - 283

EP - 300

JO - Journal of Mathematical Modelling and Algorithms

JF - Journal of Mathematical Modelling and Algorithms

SN - 1570-1166

IS - 4

ER -