L 1 C 1 polynomial spline approximation algorithms for large data sets

In this article, we address the problem of approximating data points by C ¹-smooth polynomial spline curves or surfaces using L ₁-norm. The use of this norm helps to preserve the data shape and it reduces extraneous oscillations. In our approach, we introduce a new functional which enables to control directly the distance between the data points and the resulting spline solution. The computational complexity of the minimization algorithm is nonlinear. A local minimization method using sliding windows allows to compute approximation splines within a linear complexity. This strategy seems to be more robust than a global method when applied on large data sets. When the data are noisy, we iteratively apply this method to globally smooth the solution while preserving the data shape. This method is applied to image denoising.     

Detectability of critical points of smooth functionals from their finite-dimensional approximations

Given a critical point of a C²-functional on a separable Hilbert space, we obtain sufficient conditions for it to be detectable (i.e. ‘visible’) from finite-dimensional Rayleigh-Ritz-Galerkin (RRG) approximations. While examples show that even nondegenerate critical points are, without any further restriction, not visible, we single out relevant classes of smooth functionals, e.g. the Hamiltonian action on the loop space or the functionals associated with boundary value problems for some semilinear elliptic equations, such that their nondegenerate critical points are visible from their RRG approximations.     

Polynomial approximation on the sphere using scattered data

We consider the problem of approximately reconstructing a function f defined on the surface of the unit sphere in the Euclidean space ℝ^{q +1} by using samples of f at scattered sites. A central role is played by the construction of a new operator for polynomial approximation, which is a uniformly bounded quasi‐projection in the de la Vallée Poussin style, i.e. it reproduces spherical polynomials up to a certain degree and has uniformly bounded L^p operator norm for 1 ≤ p ≤ ∞. Using certain positive quadrature rules for scattered sites due to Mhaskar, Narcowich and Ward, we discretize this operator obtaining a polynomial approximation of the target function which can be computed from scattered data and provides the same approximation degree of the best polynomial approximation. To establish the error estimates we use Marcinkiewicz–Zygmund inequalities, which we derive from our continuous approximating operator. We give concrete bounds for all constants in the Marcinkiewicz–Zygmund inequalities as well as in the error estimates. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Global convergence of the method of successive approximations on S1

The class of iterating functions of C(S¹, S¹) for which the method of successive approximations converges for any starting point is characterized; such characterization is given by (i) the existence of a fixed point; (ii) the non-existence of periodic points of an even period.     

An energy-minimization framework for monotonic cubic spline interpolation

This paper describes the use of cubic splines for interpolating monotonic data sets. Interpolating cubic splines are popular for fitting data because they use low-order polynomials and have C² continuity, a property that permits them to satisfy a desirable smoothness constraint. Unfortunately, that same constraint often violates another desirable property: monotonicity. It is possible for a set of monotonically increasing (or decreasing) data points to yield a curve that is not monotonic, i.e., the spline may oscillate. In such cases, it is necessary to sacrifice some smoothness in order to preserve monotonicity.The goal of this work is to determine the smoothest possible curve that passes through its control points while simultaneously satisfying the monotonicity constraint. We first describe a set of conditions that form the basis of the monotonic cubic spline interpolation algorithm presented in this paper. The conditions are simplified and consolidated to yield a fast method for determining monotonicity. This result is applied within an energy minimization framework to yield linear and nonlinear optimization-based methods. We consider various energy measures for the optimization objective functions. Comparisons among the different techniques are given, and superior monotonic C² cubic spline interpolation results are presented. Extensions to shape preserving splines and data smoothing are described.     

Global convergence of the method of successive approximations on S1

The class of iterating functions of C(S¹, S¹) for which the method of successive approximations converges for any starting point is characterized; such characterization is given by (i) the existence of a fixed point; (ii) the non-existence of periodic points of an even period.     

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.     

Absence of C 1- Ω-Explosion in the Space of Smooth Simplest Skew Products

We give a detailed proof of absence of a C ¹- Ω-explosion in the space of C ¹-regular simplest skew products of mappings of an interval (i.e., skew products of mappings of an interval with a closed set of periodic points). We study the influence of C ¹-perturbations (of the class of skew products) to the set of periods of the periodic points of C ¹-regular simplest skew products, and describe the peculiarities of period doubling bifurcations of the periodic points.     

A deficient spline function approximation to systems of first order differential equations

The stability of the vector-valued spline function approximations S(x) of degree m deficiency 3, i.e., S∈C^m?3, to systems of first order differential equations are investigated. The method will be shown to be A-stable for m=4, unstable and hence divergent for m?6. The method is stable form=5.     

Explicit constructions of infinite families of MSTD sets

Text

We explicitly construct infinite families of MSTD (more sums than differences) sets, i.e., sets where |A+A|>|A−A|. There are enough of these sets to prove that there exists a constant C such that at least C/r⁴ of the r² subsets of {1,…,r} are MSTD sets; thus our family is significantly denser than previous constructions (whose densities are at most f(r)/²r/2 for some polynomial f(r)). We conclude by generalizing our method to compare linear forms ?₁A+?+?nA with ?i∈{−1,1}.

Video

For a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=vIDDa1R2.     

Nonlinear data-bounded polynomial approximations and their applications in ENO methods

A class of high-order data-bounded polynomials on general meshes are derived and analyzed in the context of numerical solutions of hyperbolic equations. Such polynomials make it possible to circumvent the problem of Runge-type oscillations by adaptively varying the stencil and order used, but at the cost of only enforcing C ⁰ solution continuity at data points. It is shown that the use of these polynomials, based on extending the work of Berzins (SIAM Rev 1(4):624–627, 2007) to nonuniform meshes, provides a way to develop positivity preserving polynomial approximations of potentially high order for hyperbolic equations. The central idea is to use ENO (Essentially Non Oscillatory) type approximations but to enforce additional restrictions on how the polynomial order is increased. The question of how high a polynomial order should be used will be considered, with respect to typical numerical examples. The results show that this approach is successful but that it is necessary to provide sufficient resolution inside a front if high-order methods of this type are to be used, thus emphasizing the need to consider nonuniform meshes.     

A new approach for approximating linear elasticity problems

In this Note, we present and analyze a new method for approximating linear elasticity problems in dimension two or three. This approach directly provides approximate strains, i.e., without simultaneously approximating the displacements, in finite element spaces where the Saint Venant compatibility conditions are exactly satisfied in a weak form. To cite this article: P.G. Ciarlet, P. Ciarlet, Jr., C. R. Acad. Sci. Paris, Ser. I 346 (2008).     

A research note on design of fair surfaces over irregular domains using data-dependent triangulation

Design of fair surfaces over irregular domain is a fundamental problem in computer aided geometric design (CAGD), and has applications in engineering sciences (i.e. aircraft science, automobile science and ship science etc.). In design of fair surfaces over irregular domain defined over scattered data it was widely accepted till recently that one should use Delaunay triangulation because of its global optimum property. However, in recent times it has been shown that for continuous piecewise polynomial parametric surfaces improvements in the quality of fit can be achieved if the triangulation pattern is made dependent upon some topological property of the data set or is simply data dependent. The smoothness and fairness of surface’s planar cuts is important because not only it ensures favorable hydrodynamic drag, but also helps in reducing manhours during the production of the surface. In this paper we discuss a method for construction of C¹ piecewise polynomial parametric fair surfaces which interpolate prescribed R³${\mathfrak{R}}^3$ scattered data using spaces of parametric splines defined on R³${\mathfrak{R}}^3$ triangulation. We show that our method is more specific to the cases when the projection on 2-D plane may consist of triangles of zero area. The proposed method is fast, numerically stable and robust, and computationally inexpensive. In the present work numerical examples dealing with surfaces approximated on standard curved plates, and ship hull surface have been presented.     

Short Communication: Curvature Approximation in Images

We consider discrete planar curves as they appear in segmented images. In the literature, the curvature of such curves is often estimated via B-spline approximations or by interpolation schemes, while to the best of our knowledge current methods lack of a proof of convergence, see [2, 3]. We will not only proof the convergence of our method in the uniform norm for smooth curves, we will also show that our method is able to detect critical points (C²-singularities) of our given discrete data, i.e., points where the curvature is undefined. The main idea is to approximate the curve such that the shape of the curve is preserved. Here, we use the Schoenberg splines because of the freedom to choose the knots arbitrarily and because of their variation-diminishing property that leads to an approximation which preserves positivity, monotonicity and convexity. (© 2014 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

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.     

Local singularities of chord sets

In the present paper, we classify the local singularities of chord sets, i.e., of the envelopes of two-parameter families of straight lines connecting pairs of points on two smooth curves in ?³; we also present geometric criteria for the chord set to have a given local singularity.     

On the hardness of sampling independent sets beyond the tree threshold

We consider local Markov chain Monte–Carlo algorithms for sampling from the weighted distribution of independent sets with activity λ, where the weight of an independent set I is λ^|I|. A recent result has established that Gibbs sampling is rapidly mixing in sampling the distribution for graphs of maximum degree d and λ < λ _c (d), where λ _c (d) is the critical activity for uniqueness of the Gibbs measure (i.e., for decay of correlations with distance in the weighted distribution over independent sets) on the d-regular infinite tree. We show that for d ≥ 3, λ just above λ _c (d) with high probability over d-regular bipartite graphs, any local Markov chain Monte–Carlo algorithm takes exponential time before getting close to the stationary distribution. Our results provide a rigorous justification for “replica” method heuristics. These heuristics were invented in theoretical physics and are used in order to derive predictions on Gibbs measures on random graphs in terms of Gibbs measures on trees. A major theoretical challenge in recent years is to provide rigorous proofs for the correctness of such predictions. Our results establish such rigorous proofs for the case of hard-core model on bipartite graphs. We conjecture that λ _c is in fact the exact threshold for this computational problem, i.e., that for λ > λ _c it is NP-hard to approximate the above weighted sum over independent sets to within a factor polynomial in the size of the graph.     

An example on movable approximations of a minimal set in a continuous flow

In the present paper the study of flows on n-manifolds in particular in dimension three, e.g., R³, is motivated by the following question. Let A be a compact invariant set in a flow on X. Does every neighbourhood of A contain a movable invariant set M containing A? It is known that a stable solenoid in a flow on a 3-manifold has approximating periodic orbits in each of its neighbourhoods. The solenoid with the approximating orbits form a movable set, although the solenoid is not movable. Not many such examples are known. The main part of the paper consists of constructing an example of a set in R³ that is not stable, is not a solenoid, and is approximated by Denjoy-like invariant sets instead of periodic orbits. As in the case of a solenoid, the constructed set is an inverse limit of its approximating sets. This gives a partial answer to the above question.     

Square root 3 -Subdivision Schemes: Maximal Sum Rule Orders

Abstract. Subdivision with finitely supported masks is an efficient method to create discrete multiscale representations of smooth surfaces for CAGD applications. Recently a new subdivision scheme for triangular meshes, called $\sqrt 3$ -subdivision , has been studied. In comparison to dyadic subdivision, which is based on the dilation matrix 2I , $\sqrt 3$ -subdivision is based on a dilation M with det M=3 . This has certain advantages, for example, a slower growth for the number of control points. This paper concerns the problem of achieving maximal sum rule orders for stationary $\sqrt 3$ -subdivision schemes with given mask support, which is important because the sum rule order characterizes the order of the polynomial reproduction, and provides an upper bound on the Sobolev smoothness of the surface. We study both interpolating and approximating schemes for a natural family of symmetric mask support sets related to squares of sidelength 2n in Z ² , and obtain exact formulas for the maximal sum rule order for arbitrary n . For approximating schemes, the solution is simple, and schemes with maximal sum rule order are realized by an explicit family of schemes based on repeated averaging [15]. In the interpolating case, we use properties of multivariate Lagrange polynomial interpolation to prove the existence of interpolating schemes with maximal sum rule orders. These can be found by solving a linear system which can be reduced in size by using symmetries. From this, we construct some new examples of smooth (C ² ,C ³ ) interpolating $\sqrt 3$ -subdivision schemes with maximal sum rule order and symmetric masks. The construction of associated dual schemes is also discussed.