Monotone and Convex C 1 Hermite Interpolants Generated by a Subdivision Scheme

   Abstract. We propose C ¹ Hermite interpolants generated by the general subdivision scheme introduced by Merrien [17] and satisfying monotonicity or convexity constraints. For arbitrary values and slopes of a given function f at the end-points of a bounded interval, which are compatible with the contraints, the given algorithms construct shape-preserving interpolants. Moreover, these algorithms are quite simple and fast as well as adapted to CAGD. We also give error estimates in the case of interpolation of smooth functions.     

A recursive method for computing interpolants

In this paper, we describe a recursive method for computing interpolants defined in a space spanned by a finite number of continuous functions in R^d${\mathbb{R}}^d$. We apply this method to construct several interpolants such as spline interpolants, tensor product interpolants and multivariate polynomial interpolants. We also give a simple algorithm for solving a multivariate polynomial interpolation problem and constructing the minimal interpolation space for a given finite set of interpolation points.     

On polyharmonic interpolation

In the present paper we will introduce a new approach to multivariate interpolation by employing polyharmonic functions as interpolants, i.e. by solutions of higher order elliptic equations. We assume that the data arise from C^∞ or analytic functions in the ball BR. We prove two main results on the interpolation of C^∞ or analytic functions f in the ball BR by polyharmonic functions h of a given order of polyharmonicity p.     

Tautologies with a unique craig interpolant,uniform vs. nonuniform complexity

If S?{0,1};^* and S′ = {0,1}^*\sbS are both recognized within a certain nondeterministic time bound T then, in not much more time, one can write down tautologies A_n→A′_n with unique interpolants I_n that define S∩{0,1}ⁿ; hence, if one can rapidly find unique interpolants, then one can recognize S within deterministic time T^p for some fixed p\s>0. In general, complexity measures for the problem of finding unique interpolants in sentential logic yield new relations between circuit depth and nondeterministic Turing time, as well as between proof length and the complexity of decision procedures of logical theories.     

First order hermite interpolation with spherical Pythagorean-hodograph curves

The general stereographic projection which maps a point on a sphere with arbitrary radius to a point on a plane stereographically and its inverse projection have the Pythagorean-hodograph (PH) preserving property in the sense that they map a PH curve to another PH curve. Upon this fact, for given spatialC ¹ Hermite data, we construct a spatial PH curve on a sphere that is aC ¹ Hermite interpolant of the given data as follows: First, we solveC ¹ Hermite interpolation problem for the stereographically projected planar data of the given data in ?³ with planar PH curves expressed in the complex representation. Second, we construct spherical PH curves which are interpolants for the given data in ?³ using the inverse general stereographic projection.     

Bernstein-Type Bases and Corner Cutting Algorithms for C 1 Merrien's Curves

Bernstein bases, control polygons and corner-cutting algorithms are defined for C ¹ Merrien's curves introduced in [7]. The convergence of these algorithms is proved for two specific families of curves. Results on monotone and convex interpolants which have been proved in [8] by Merrien and the author are also recovered.     

Positivity of cubic polynomials on intervals and positive spline interpolation

A criterion for the positivity of a cubic polynomial on a given interval is derived. By means of this result a necessary and sufficient condition is given under which cubicC ¹-spline interpolants are nonnegative. Further, since such interpolants are not uniquely determined, for selecting one of them the geometric curvature is minimized. The arising optimization problem is solved numerically via dualization.     

Range restricted interpolation using Gregory's rational cubic splines

The construction of range restricted univariate and bivariate interpolants to gridded data is considered. We apply Gregory's rational cubic C¹ splines as well as related rational quintic C² splines. Assume that the lower and upper obstacles are compatible with the data set. Then the tension parameters occurring in the mentioned spline classes can be always determined in such a way that range restricted interpolation is successful.     

Lower complexity bounds for interpolation algorithms

We introduce and discuss a new computational model for the Hermite-Lagrange interpolation with nonlinear classes of polynomial interpolants. We distinguish between an interpolation problem and an algorithm that solves it. Our model includes also coalescence phenomena and captures a large variety of known Hermite-Lagrange interpolation problems and algorithms. Like in traditional Hermite-Lagrange interpolation, our model is based on the execution of arithmetic operations (including divisions) in the field where the data (nodes and values) are interpreted and arithmetic operations are counted at unit cost. This leads us to a new view of rational functions and maps defined on arbitrary constructible subsets of complex affine spaces. For this purpose we have to develop new tools in algebraic geometry which themselves are mainly based on Zariski’s Main Theorem and the theory of places (or equivalently: valuations). We finish this paper by exhibiting two examples of Lagrange interpolation problems with nonlinear classes of interpolants, which do not admit efficient interpolation algorithms (one of these interpolation problems requires even an exponential quantity of arithmetic operations in terms of the number of the given nodes in order to represent some of the interpolants).In other words, classic Lagrange interpolation algorithms are asymptotically optimal for the solution of these selected interpolation problems and nothing is gained by allowing interpolation algorithms and classes of interpolants to be nonlinear. We show also that classic Lagrange interpolation algorithms are almost optimal for generic nodes and values. This generic data cannot be substantially compressed by using nonlinear techniques.We finish this paper highlighting the close connection of our complexity results in Hermite-Lagrange interpolation with a modern trend in software engineering: architecture tradeoff analysis methods (ATAM).     

Order of linear approximation from shift-invariant spaces

A Fourier analysis approach is taken to investigate the approximation order of scaled versions of certain linear operators into shift-invariant subspaces ofL ₂(R ^d ). Quasi-interpolants and cardinal interpolants are special operators of this type, and we give a complete characterization of the order in terms of some type of ellipticity condition for a related function. We apply these results by showing that theL ₂-approximation order of a closed shift-invariant subspace can often be realized by such an operator.     

Deciding the existence of uniform interpolants over transitive models

We consider the problem of the existence of uniform interpolants in the modal logic K4. We first prove that all ${\square}$ -free formulas have uniform interpolants in this logic. In the general case, we shall prove that given a modal formula ${\phi}$ and a sublanguage L of the language of the formula, we can decide whether ${\phi}$ has a uniform interpolant with respect to L in K4. The ${\square}$ -free case is proved using a reduction to the G?del L?b Logic GL, while in the general case we prove that the question of whether a modal formula has uniform interpolants over transitive frames can be reduced to a decidable expressivity problem on the???-calculus.     

Convergence of local variational spline interpolation

In this paper we first revisit a classical problem of computing variational splines. We propose to compute local variational splines in the sense that they are interpolatory splines which minimize the energy norm over a subinterval. We shall show that the error between local and global variational spline interpolants decays exponentially over a fixed subinterval as the support of the local variational spline increases. By piecing together these locally defined splines, one can obtain a very good C⁰ approximation of the global variational spline. Finally we generalize this idea to approximate global tensor product B-spline interpolatory surfaces.     

向量值有理插值存在性的一种判别方法

对于向量值有理插值的计算,目前已经有多种求解算法.但其存在性的判别方法及其证明在现有的文献中还没有见到.这里利用标量有理插值函数插值存在性的思想,引入Newton基函数,给出并证明了向量值有理插值存在性的一种判别方法.同时给出有理插值函数的分子和分母的显式表达式,最后的实例说明了它的有效性.     

Scattered data interpolation based upon generalized minimum norm networks

A generalization of G. M. Nielson's method for bivariate scattered data interpolation based upon a minimum norm network is presented. The essential part of the new method is the use of a variational principle for definition of function values as well as cross-boundary derivatives over the edges of a triangulation of the data points. We mainly discuss the case ofC ² interpolants and present some examples including quality control with systems of isophotes.     

Probabilistic analysis of some euclidean clustering problems

We are given n points distributed randomly in a compact region D of R^m. We consider various optimisation problems associated with partitioning this set of points into k subsets. For each problem we demonstrate lower bounds which are satisfied with high probability. For the case where D is a hypercube we use a partitioning technique to give deterministic upper bounds and to construct algorithms which with high probability can be made arbitrarily accurate in polynomial time for a given required accuracy.     

Unified Representations of Nonlinear Splines

Golomb and Jerome's framework is modified and extended. The new framework is more general since it also handles interpolants which are not allowed to “slide” at the nodes. The space of interpolants of variable length is shown to be a smooth manifold. If the length is fixed, and there are no nodes, then the space of interpolants is a manifold. When there is at least one node, and at least one node is not on the line segment between the endpoints, then the space of interpolants of fixed length is a smooth manifold. Sufficient conditions are given which ensure the space of interpolants continues to be a smooth manifold in the presence of additional constraints such as clamping and pinning. A new fundamental finite-dimensional equation is derived. When it is solved it yields all nonlinear splines, and every nonlinear spline appears in this way. An important feature is that the same symbolic equation is used for all possible combinations of the constraints considered. It is shown how to take the solutions of the fundamental equation and use them to express the corresponding nonlinear splines in terms of a pair of elliptic functions. An inequality is derived that specifies which elliptic function appears along each section of the spline. The nonlinear splines are in a unified way shown to beC²for all possible combinations of the constraints considered.     

AR quivers, exceptional sequences and algorithms in derived Hall algebras

Consider the canonical isomorphism between the positive part U ⁺ of the quantum group U _q (g) and the Hall algebra H(Λ), where the semisimple Lie algebra g and the finite-dimensional hereditary algebra Λ share a Dynkin diagram. Chen and Xiao have given two algorithms to decompose the root vectors into linear combinations of monomials of Chevalley generators of U ⁺, respectively induced by the braid group action on the exceptional sequences of Λ-modules and the structure of the Auslander-Reiten quiver of Λ. In this paper, we obtain the corresponding algorithms for the derived Hall algebra DH(Λ), which was introduced by Toën. We show that both algorithms are applicable to the lattice algebra and Heisenberg double in the sense of Kapranov. All the new recursive formulae have the same flavor with the quantum Serre relations.     

Dynamic programming algorithms for picture comparison

Two-dimensional arrays can be compared by a generalization of dynamic programming algorithms for string comparison. Earlier algorithms have computational complexity O(N⁶) for comparison of two N × N arrays. The computational complexity is reduced to O(N⁴) in general and O(N²) algorithms are pointed out for the range limited case. An example is given to illustrate the lack of knowledge of mathematical properties of these algorithms. The problem of finding an algorithm to compute the minimum number of insertions, deletions, and substitutions to transform one array into another remains open.     

Power Series Kernels

We introduce a class of analytic positive definite multivariate kernels which includes infinite dot product kernels as sometimes used in machine learning, certain new nonlinearly factorizable kernels, and a kernel which is closely related to the Gaussian. Each such kernel reproduces in a certain “native” Hilbert space of multivariate analytic functions. If functions from this space are interpolated in scattered locations by translates of the kernel, we prove spectral convergence rates of the interpolants and all derivatives. By truncation of the power series of the kernel-based interpolants, we constructively generalize the classical Bernstein theorem concerning polynomial approximation of analytic functions to the multivariate case. An application to machine learning algorithms is presented.      

Construction Algorithms for Good Extensible Lattice Rules

Extensible (polynomial) lattice rules have the property that the number N of points in the node set may be increased while retaining the existing points. It was shown by Hickernell and Niederreiter in a nonconstructive manner that there exist generating vectors for extensible integration lattices of excellent quality for N=b,b ²,b ³,…, where b is a given integer greater than 1. Similar results were proved by Niederreiter for polynomial lattices. In this paper we provide construction algorithms for good extensible lattice rules. We treat the classical as well as the polynomial case.