Taylorian fields and subdivision algorithms

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 classC ^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, aC ¹ (orC ^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.     

Convergent Vector and Hermite Subdivision Schemes

Hermite subdivision schemes have been studied by Merrien, Dyn, and Levin and they appear to be very different from subdivision schemes analyzed before since the rules depend on the subdivision level. As suggested by Dyn and Levin, it is possible to transform the initial scheme into a uniform stationary vector subdivision scheme which can be handled more easily.With this transformation, the study of convergence of Hermite subdivision schemes is reduced to that of vector stationary subdivision schemes. We propose a first criterion for C⁰-convergence for a large class of vector subdivision schemes. This gives a criterion for C¹-convergence of Hermite subdivision schemes. It can be noticed that these schemes do not have to be interpolatory. We conclude by investigating spectral properties of Hermite schemes and other necessary/sufficient conditions of convergence.     

Approximation order of interpolatory nonlinear subdivision schemes

Linear interpolatory subdivision schemes of C^r smoothness have approximation order at least r+1. The present paper extends this result to nonlinear univariate schemes which are in proximity with linear schemes in a certain specific sense. The results apply to nonlinear subdivision schemes in Lie groups and in surfaces which are obtained from linear subdivision schemes. We indicate how to extend the results to the multivariate case.     

A constructive algebraic strategy for interpolatory subdivision schemes induced by bivariate box splines

This paper describes an algebraic construction of bivariate interpolatory subdivision masks induced by three-directional box spline subdivision schemes. Specifically, given a three-directional box spline, we address the problem of defining a corresponding interpolatory subdivision scheme by constructing an appropriate correction mask to convolve with the three-directional box spline mask. The proposed approach is based on the analysis of certain polynomial identities in two variables and leads to interesting new interpolatory bivariate subdivision schemes.     

Smoothness of Stationary Subdivision on Irregular Meshes

We derive necessary and sufficient conditions for tangent plane and C ^k -continuity of stationary subdivision schemes near extraordinary vertices. Our criteria generalize most previously known conditions. We introduce a new approach to analysis of subdivision surfaces based on the idea of the universal surface . Any subdivision surface can be locally represented as a projection of the universal surface, which is uniquely defined by the subdivision scheme. This approach provides us with a more intuitive geometric understanding of subdivision near extraordinary vertices. February 16, 1998. Date revised: January 27, 1999. Date accepted: April 2, 1999.     

Using Laurent polynomial representation for the analysis of non‐uniform binary subdivision schemes

Non‐uniform binary linear subdivision schemes, with finite masks, over uniform grids, are studied. A Laurent polynomial representation is suggested and the basic operations required for smoothness analysis are presented. As an example it is shown that the interpolatory 4‐point scheme is C ¹ with an almost arbitrary non‐uniform choice of the free parameter. This revised version was published online in June 2006 with corrections to the Cover Date.     

Hermite Subdivision Schemes and Taylor Polynomials

We propose a general study of the convergence of a Hermite subdivision scheme ℋ of degree d>0 in dimension 1. This is done by linking Hermite subdivision schemes and Taylor polynomials and by associating a so-called Taylor subdivision (vector) scheme . The main point of investigation is a spectral condition. If the subdivision scheme of the finite differences of is contractive, then is C ⁰ and ℋ is C ^d . We apply this result to two families of Hermite subdivision schemes. The first one is interpolatory; the second one is a kind of corner cutting. Both of them use the Tchakalov-Obreshkov interpolation polynomial.      

Non-uniform interpolatory curve subdivision with edge parameters built upon compactly supported fundamental splines

In this paper we present a family of Non-Uniform Local Interpolatory (NULI) subdivision schemes, derived from compactly supported interpolatory fundamental splines with non-uniform knots (NULIFS). For this spline family, the knot-partition is defined by a sequence of break points and by one additional knot, arbitrarily placed along each knot-interval. The resulting refinement algorithms are linear and turn out to contain a set of edge parameters that, when fixed to a value in the range [0,1], allow us to achieve special shape features by simply moving each auxiliary knot between the break points. Among all the members of this new family of schemes, we will then especially analyze the NULI 4-point refinement. This subdivision scheme has all the fundamental features of the quadratic fundamental spline basis it is originated from, namely compact support, C ¹ smoothness, second order polynomials reproduction and approximation order 3. In addition the NULI 4-point subdivision algorithm has the possibility of setting consecutive edge parameters to simulate double and triple knots—that are not considered by the authors of the corresponding spline basis—thus allowing for limit curves with crease vertices, without using an ad hoc mask. Numerical examples and comparisons with other methods will be given to the aim of illustrating the performance of the NULI 4-point scheme in the case of highly non-uniform initial data.     

Analysis of subdivision schemes for nets of functions by proximity and controllability

In this paper we develop tools for the analysis of net subdivision schemes, schemes which recursively refine nets of bivariate continuous functions defined on grids of lines, and generate denser and denser nets. Sufficient conditions for the convergence of such a sequence of refined nets, and for the smoothness of the limit function, are derived in terms of proximity to a bivariate linear subdivision scheme refining points, under conditions controlling some aspects of the univariate functions of the generated nets. Approximation orders of net subdivision schemes, which are in proximity with positive schemes refining points are also derived. The paper concludes with the construction of a family of blending spline-type net subdivision schemes, and with their analysis by the tools presented in the paper. This family is a new example of net subdivision schemes generating C¹ limits with approximation order 2.     

Stationary binary subdivision schemes using radial basis function interpolation

A new family of interpolatory stationary subdivision schemes is introduced by using radial basis function interpolation. This work extends earlier studies on interpolatory stationary subdivision schemes in two aspects. First, it provides a wider class of interpolatory schemes; each 2L-point interpolatory scheme has the freedom of choosing a degree (say, m) of polynomial reproducing. Depending on the combination (2L,m), the proposed scheme suggests different subdivision rules. Second, the scheme turns out to be a 2L-point interpolatory scheme with a tension parameter. The conditions for convergence and smoothness are also studied. Dedicated to Prof. Charles A. Micchelli on the occasion of his 60th birthday Mathematics subject classifications (2000) 41A05, 41A25, 41A30, 65D10, 65D17. Byung-Gook Lee: This work was done as a part of Information & Communication fundamental Technology Research Program supported by Ministry of the Information & Communication in Republic of Korea. Jungho Yoon: Corresponding author. Supported by the Korea Science and Engineering Foundation grant (KOSEF R06-2002-012-01001).     

Noninterpolatory Hermite subdivision schemes

Bivariate interpolatory Hermite subdivision schemes have recently been applied to build free-form subdivision surfaces. It is well known to geometric modelling practitioners that interpolatory schemes typically lead to ``unfair" surfaces--surfaces with unwanted wiggles or undulations--and noninterpolatory (a.k.a. approximating in the CAGD community) schemes are much preferred in geometric modelling applications. In this article, we introduce, analyze and construct noninterpolatory Hermite subdivision schemes, a class of vector subdivision schemes which can be applied to iteratively refine Hermite data in a not necessarily interpolatory fashion. We also study symmetry properties of such subdivision schemes which are crucial for application in free-form subdivision surfaces.

A key step in our mathematical analysis of Hermite type subdivision schemes is that we make use of the strong convergence theory of refinement equations to convert a prescribed geometric condition on the subdivision scheme--namely, the subdivision scheme is of Hermite type--to an algebraic condition on the subdivision mask. The latter algebraic condition can then be used in a computational framework to construct specific schemes.

     

From approximating to interpolatory non-stationary subdivision schemes with the same generation properties

In this paper we describe a general, computationally feasible strategy to deduce a family of interpolatory non-stationary subdivision schemes from a symmetric non-stationary, non-interpolatory one satisfying quite mild assumptions. To achieve this result we extend our previous work (Conti et al., Linear Algebra Appl 431(10):1971?C1987, 2009) to full generality by removing additional assumptions on the input symbols. For the so obtained interpolatory schemes we prove that they are capable of reproducing the same space of exponential polynomials as the one generated by the original approximating scheme. Moreover, we specialize the computational methods for the case of symbols obtained by shifted non-stationary affine combinations of exponential B-splines, that are at the basis of most non-stationary subdivision schemes. In this case we find that the associated family of interpolatory symbols can be determined to satisfy a suitable set of generalized interpolating conditions at the set of the zeros (with reversed signs) of the input symbol. Finally, we discuss some computational examples by showing that the proposed approach can yield novel smooth non-stationary interpolatory subdivision schemes possessing very interesting reproduction properties.     

Subdivision Schemes of Sets and the Approximation of Set-Valued Functions in the Symmetric Difference Metric

In this work we construct subdivision schemes refining general subsets of ? ⁿ and study their applications to the approximation of set-valued functions. Differently from previous works on set-valued approximation, our methods are developed and analyzed in the metric space of Lebesgue measurable sets endowed with the symmetric difference metric. The construction of the set-valued subdivision schemes is based on a new weighted average of two sets, which is defined for positive weights (corresponding to interpolation) and also when one weight is negative (corresponding to extrapolation). Using the new average with positive weights, we adapt to sets spline subdivision schemes computed by the Lane–Riesenfeld algorithm, which requires only averages of pairs of numbers. The averages of numbers are then replaced by the new averages of pairs of sets. Among other features of the resulting set-valued subdivision schemes, we prove their monotonicity preservation property. Using the new weighted average of sets with both positive and negative weights, we adapt to sets the 4-point interpolatory subdivision scheme. Finally, we discuss the extension of the results obtained in metric spaces of sets, to general metric spaces endowed with an averaging operation satisfying certain properties.     

On polynomial symbols for subdivision schemes

Given a dilation matrix A :ℤ^d→ℤ^d, and G a complete set of coset representatives of 2π(A ^−Tℤ^d/ℤ^d), we consider polynomial solutions M to the equation ∑ _g∈G M(ξ+g)=1 with the constraints that M≥0 and M(0)=1. We prove that the full class of such functions can be generated using polynomial convolution kernels. Trigonometric polynomials of this type play an important role as symbols for interpolatory subdivision schemes. For isotropic dilation matrices, we use the method introduced to construct symbols for interpolatory subdivision schemes satisfying Strang–Fix conditions of arbitrary order. Research partially supported by the Danish Technical Science Foundation, Grant No. 9701481, and by the Danish SNF-PDE network.     

基于逼近型细分的诱导细分格式

利用逼近型细分构造插值型细分是细分领域中的一个重要问题,目前可以给出插值型细分生成函数的研究还非常少.本文给出一个生成函数的统一公式,该公式由逼近型细分的生成函数与一个子生成函数构成.该公式对应一个插值型细分或者逼近型细分,这个取决于子生成函数的选取.该公式在理论和实际中都很重要.首先,这个公式适用于任意伸缩矩阵的多元基本型细分;其次,不论是一元细分还是多元细分,推导这个统一公式都不需要求解线性方程组;再次,这个公式具有显著的几何意义,应用方便;最后,从理论上分析诱导细分的零条件和多项式再生性,本文发现这些性质不仅与逼近型细分的零条件有关,而且与逼近型细分的多项式再生性有关,从而对细分格式的构造有指导意义.本文给出3个例子来说明这个统一公式.     

Three-Class Association Schemes on Galois Rings in Characteristic 4

Small feasible parameters for ``nontrivial' symmetric three-class association schemes were listed in a paper of van Dam. This work addresses the question of existence for three-class association schemes on 4ⁿ vertices. Several families of three-class symmetric schemes are constructed in association schemes of Galois rings of characteristic 4.     

Convergence and smoothness analysis of subdivision rules in Riemannian and symmetric spaces

After a discussion on definability of invariant subdivision rules we discuss rules for sequential data living in Riemannian manifolds and in symmetric spaces, having in mind the space of positive definite matrices as a major example. We show that subdivision rules defined with intrinsic means in Cartan-Hadamard manifolds converge for all input data, which is a much stronger result than those usually available for manifold subdivision rules. We also show weaker convergence results which are true in general but apply only to dense enough input data. Finally we discuss C ¹ and C ² smoothness of limit curves.     

A unified three point approximating subdivision scheme

In this paper,we propose a three point approximating subdivision scheme,with three shape parameters,that unifies three different existing three point approximating schemes.Some sufficient conditions for subdivision curve C0 to C3 continuity and convergence of the scheme for generating tensor product surfaces for certain ranges of parameters by using Laurent polynomial method are discussed.The systems of curve and surface design based on our scheme have been developed successfully in garment CAD especially for clothes modelling.