检索结果-内蒙古大学图书馆

subdivision algorithms CONVERGE QUADRATICALLY

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 1986年第2期16卷 145-158页

作者： DAHMEN, W UNIV BIELEFELD FAK MATHD-4800 BIELEFELDFED REP GER

This paper is concerned with determining the exact convergence rates of subdivision algorithms for various settings of polynomial and spline curve or surface representations.

关键词： subdivision algorithms convergence rates B -splines Bernstein—Bézier representations

来源：评论

学校读者我要写书评

暂无评论

Local energy-optimizing subdivision algorithms

引用

COMPUTER AIDED GEOMETRIC DESIGN 2008年第3期25卷 137-147页

作者： Ginkel, I. Umlauf, G. Univ Kaiserslautern Dept Comp Sci Geometr Algorithms Grp D-67653 Kaiserslautern Germany

In this paper a method is presented to fair the limit surface of a subdivision algorithm locally around an extraordinary point. The dominant six eigenvalues of the subdivision matrix have to satisfy linear and quadratic equality- and inequality-constraints in order to guarantee normal-continuity and bounded curvature at the extraordinary point. All other eigenvalues can be chosen arbitrarily within certain intervals and therefore can be used to optimize the shape of the subdivision surface by minimizing quadratic energy functionals. Additionally, if the sub- and subsub-dominant eigenvalues vary within predefined intervals, C-1-regularity of the surface and locality of the stencils can be guaranteed, although eigenvectors are changed. (C) 2007 Elsevier B.V. All rights reserved.

关键词： subdivision algorithms algorithm of loop algorithm of Catmull-Clark constrained optimization eigenvalues thin-plate energy

来源：评论

学校读者我要写书评

暂无评论

ON THE CONVERGENCE-RATES OF subdivision algorithms FOR BOX SPLINE SURFACES

引用

CONSTRUCTIVE APPROXIMATION 1985年第4期1卷 305-322页

作者： DAHMEN, W DYN, N LEVIN, D UNIV BIELEFELD FAK MATHD-4800 BIELEFELDFED REP GER TEL AVIV UNIV SCH MATH SCIIL-69978 TEL AVIVISRAEL

Dahmen and Micchelli [8] have shown that in general the coefficients of the refined control nets of a box spline surface converge to the surface at (at least) the rate of the refinement. The purpose of this article is to show that under mild additional assumptions the convergence rate is even quadratic. Although this rate is in general best possible, we point out under what circumstances even higher rates are obtained (locally).

关键词： AMS classification: 41A15 Box spline Control net Convergence rate subdivision algorithms

来源：评论

学校读者我要写书评

暂无评论

Near optimal subdivision algorithms for real root isolation

引用

JOURNAL OF SYMBOLIC COMPUTATION 2017年 83卷 4-35页

作者： Batra, Prashant Sharma, Vikram Tech Univ Hamburg Hamburg Germany Inst Math Sci Madras 600113 Tamil Nadu India

Isolating real roots of a square-free polynomial in a given interval is a fundamental problem in computational algebra. subdivision based algorithms are a standard approach to solve this problem. For instance, Sturm's method, or various algorithms based on the Descartes's rule of signs. For the benchmark problem of isolating all the real roots of a polynomial of degree n and root separation a, the size of the subdivision tree of most of these algorithms is bounded by O (log 1/sigma) (assume sigma < 1). Moreover, it is known that this is optimal for subdivision algorithms that perform uniform subdivision, i.e., the width of the interval decreases by some constant. Recently Sagraloff (2012) and Sagraloff-Mehlhorn (2016) have developed algorithms for real root isolation that combine subdivision with Newton iteration to reduce the size of the subdivision tree to O (n(log(n log 1/sigma))). We describe a subroutine that reduces the size of the subdivision tree of any subdivision algorithm for real root isolation. The subdivision tree size of our algorithm using predicates based on either the Descartes's rule of signs or Sturm sequences is bounded by O (n logn), which is close to the optimal value of O (n). The corresponding bound for the algorithm EVAL, which uses certain interval-arithmetic based predicates, is O (n(2) log n). Our analysis differs in two key aspects from earlier approaches. First, we use the general technique of continuous amortization from Burr Krahmer Yap (2009), and extend it to handle non-uniform subdivisions;second, we use the geometry of clusters of roots instead of root bounds. The latter aspect enables us to derive a bound on the subdivision tree that is independent of the root separation sigma. The number of Newton iterations is bounded by O (n loglog(1/sigma)). (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Real root isolation subdivision algorithms Newton diagram Continuous amortization Integral analysis

来源：评论

学校读者我要写书评

暂无评论

Taylorian fields and subdivision algorithms

引用

Numerical algorithms 1991年第2期1卷 225-235页

作者： Le Méhauté, A. Laboratoire d'Analyse Numérique et d'Optimisation Université de Lille 1 Flandres-Artois Villeneuve d'Ascq Cedex 59655 France

Some recents papers [3,8] provide a new approach for the concept of subdivision algorithms, widely used in CAGD: they develop the idea of interpolatory subdivision schemes for curves. In this paper, we show how the old results of H. Whitney [13,14] on Taylorian fields giving necessary and sufficient conditions for a function to be of class C^k on a compact provide also necessary and sufficient conditions which can be used to construct interpolatory subdivision schemes, in order to obtain, at the limit, a C¹ (or C^k, k>1 eventually) function. Moreover, we give general results for the approximation properties of these schemes, and error bounds for the approximation of a given function. © 1991 J.C. Baltzer A.G. Scientific Publishing Company.

关键词： CAGD extension theorems interpolation of functions shape preservation subdivision algorithms Subject Classifications: AMS (Mos), 65D05 Taylorian fields

来源：评论

学校读者我要写书评

暂无评论

Near Optimal subdivision algorithms for Real Root Isolation 15

Near Optimal Subdivision Algorithms for Real Root Isolation

引用

ACM International Symposium on Symbolic and Algebraic Computation (ISSAC)

作者： Sharma, Vikram Batra, Prashant Inst Math Sci Chennai 600113 Tamil Nadu India Tech Univ Hamburg Hamburg Germany

ISBN: (纸本)9781450334358

Isolating real roots of a square-free polynomial in a given interval is a fundamental problem. subdivision based algorithms are a standard approach to solve this problem. E.g., Sturm's method, or various algorithms based on the Descartes's rule of signs. For isolating all the real roots of a degree n polynomial with root separation sigma, the subdivision tree size of most of these algorithms is bounded by O(log 1/sigma) (assume sigma < 1). Recently Sagraloff (2012) and Sagraloff-Mehlhorn (2013) have developed algorithms that combine subdivision with Newton iteration to reduce the size of the subdivision tree to O (n(log(n log 1/sigma))). Their algorithms and analysis crucially depend on the terminating predicates. We describe a subroutine that improves the running time of any subdivision algorithm for real root isolation. The subdivision tree size of our algorithm using predicates based on the Descartes's rule of signs is bounded by O(n log n). Our analysis differs in two key aspects from earlier approaches. First, we use the general technique of continuous amortization from Burr-Krahmer-Yap (2009), and hence the analysis extends to other predicates;and second, we use the geometry of clusters of roots instead of root bounds.

关键词： Real root isolation subdivision algorithms Newton diagram Continuous amortization Integral analysis

来源：评论

学校读者我要写书评

暂无评论

Evaluation and subdivision algorithms for general classes of totally positive rational bases

引用

COMPUTER AIDED GEOMETRIC DESIGN 2020年 81卷 101900-101900页

作者： Mainar, E. Pena, J. M. Rubio, B. Univ Zaragoza Dept Matemat Aplicada IUMA Zaragoza Spain

Weighted phi-transformed systems include many systems of functions useful in C.A.G.D. It is proved that these systems inherit some geometric properties of a given initial system, such as shape preservation or optimal shape preservation. A general class of important rational bases can be obtained as a particular example of weighted phi-transformed systems. For these bases, evaluation and subdivision algorithms are presented. Some relevant applications are pointed out. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Normalized totally positive basis Normalized B-basis Rational basis de Casteljau algorithms subdivision algorithms

来源：评论

学校读者我要写书评

暂无评论

A unified subdivision approach for multi-dimensional non-manifold modeling

引用

COMPUTER-AIDED DESIGN 2006年第7期38卷 770-785页

作者： Chang, Yu-Sung Qin, Hong Wolfram Res Inc Champaign IL 61820 USA SUNY Stony Brook Dept Comp Sci Stony Brook NY 11794 USA

This paper presents a new unified subdivision scheme that is defined over a k-simplicial complex in n-D space with k <= 3. We first present a series of definitions to facilitate topological inquiries during the subdivision process. The scheme is derived from the double (k + 1)-directional box splines over k-simplicial domains. Thus, it guarantees a certain level of smoothness in the limit on a regular mesh. The subdivision rules are modified by spatial averaging to guarantee Cl smoothness near extraordinary cases. Within a single framework, we combine the subdivision rules that can produce 1-, 2-, and 3-manifolds in arbitrary n-D space. Possible solutions for non-manifold regions between the manifolds with different dimensions are suggested as a form of selective subdivision rules according to user preference. We briefly describe the subdivision matrix analysis to ensure a reasonable smoothness across extraordinary topologies, and empirical results support our assumption. In addition, through modifications, we show that the scheme can easily represent objects with singularities, such as cusps, creases, or corners. We further develop local adaptive refinement rules that can achieve level-of-detail control for hierarchical modeling. Our implementation is based on the topological properties of a simplicial domain. Therefore, it is flexible and extendable. We also develop a solid modeling system founded on our subdivision schemes to show potential benefits of our work in industrial design, geometric processing, and other applications. (C) 2006 Elsevier Ltd. All rights reserved.

关键词： subdivision algorithms geometric and topological representations solid modeling multiresolution models volumetric meshes

来源：评论

学校读者我要写书评

暂无评论

A new subdivision algorithm for the flow propagation using polynomial algebras

引用

COMMUNICATIONS IN NONLINEAR SCIENCE AND NUMERICAL SIMULATION 2018年 61卷 37-53页

作者： Perez-Palau, Daniel Gomez, Gerard Masdemont, Josep J. CNES 18 Ave Edouard Belin F-31401 Toulouse France Univ Barcelona Gran Via 585 E-08007 Barcelona Spain IEEC Gran Via 585 Barcelona 08007 Spain Univ Politecn Cataluna Diagonal 647 E-08028 Barcelona Spain IEEC Diagonal 647 Barcelona 08028 Spain

The Jet Transport method has emerged as a powerful tool for the numerical integration of ordinary differential equations;it uses polynomial expansions to approximate the flow map associated to the differential equation in the neighbourhood of a reference solution. One of the main drawbacks of the method is that the region of accuracy becomes smaller along the integration. In this paper we introduce a procedure to determine a ball covering the set of given initial conditions that keeps the accuracy of the integration within a selected threshold. The paper gives detailed explanations of the algorithm illustrated with some examples of applicability, as well as a comparison with a previous existing method for the same purpose. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Jet transport Polynomial algebra subdivision algorithms ODE polynomial propagation

来源：评论

学校读者我要写书评

暂无评论

DigitalSculpture:: a subdivision-based approach to interactive implicit surface modeling

引用

GRAPHICAL MODELS 2005年第4期67卷 347-369页

作者： McDonnell, KT Chang, YS Qin, H SUNY Stony Brook Dept Comp Sci Stony Brook NY 11794 USA

This paper presents DigitalSculpture, an interactive sculpting framework founded upon iso-surfaces extracted from recursively subdivided, 3D irregular grids. Our unique implicit surface model arises from an interpolatory, volumetric subdivision scheme that is C-1 continuous across the domains defined by arbitrary 3D irregular grids. We assign scalar coefficients and color to each control vertex and allow these quantities to participate in the volumetric subdivision of irregular grids. In the subdivision limit, a virtual sculpture is obtained by extracting the zero-level from the volumetric, scalar field defined over the irregular grid. This novel shape geometry extends concepts from solid modeling, recursive subdivision, and implicit surfaces;facilitates many techniques for interactive sculpting;permits rapid, local evaluation of iso-surfaces;and affords level-of-detail control of the sculpted surfaces. (c) 2004 Elsevier Inc. All rights reserved.

关键词： implicit surfaces interactive sculpting subdivision algorithms solid modeling

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：