Variation diminishing property

Last updated
Sample curves (red) with their polygons (grey). Bezier curves.png
Sample curves (red) with their polygons (grey).

In mathematics, the variation diminishing property of certain mathematical objects involves diminishing the number of changes in sign (positive to negative or vice versa).

Contents

Variation diminishing property for Bézier curves

The variation diminishing property of Bézier curves is that they are smoother than the polygon formed by their control points. If a line is drawn through the curve, the number of intersections with the curve will be less than or equal to the number of intersections with the control polygon. In other words, for a Bézier curve B defined by the control polygon P, the curve will have no more intersection with any plane as that plane has with P. This may be generalised into higher dimensions. [1]

This property was first studied by Isaac Jacob Schoenberg in his 1930 paper, Über variationsvermindernde lineare Transformationen. [2] He went on to derive it by a transformation of Descartes' rule of signs. [3]

Proof

The proof uses the process of repeated degree elevation of Bézier curve. The process of degree elevation for Bézier curves can be considered an instance of piecewise linear interpolation. Piecewise linear interpolation can be shown to be variation diminishing. [4] Thus, if R1, R2, R3 and so on denote the set of polygons obtained by the degree elevation of the initial control polygon R, then it can be shown that

Using the above points, we say that since the Bézier curve B is the limit of these polygons as r goes to , it will have fewer intersections with a given plane than Ri for all i, and in particular fewer intersections that the original control polygon R. This is the statement of the variation diminishing property.

Totally positive matrices

The variation diminishing property of totally positive matrices is a consequence of their decomposition into products of Jacobi matrices.

The existence of the decomposition follows from the Gauss–Jordan triangulation algorithm. It follows that we need only prove the VD property for a Jacobi matrix.

The blocks of Dirichlet-to-Neumann maps of planar graphs have the variation diminishing property.

Related Research Articles

<span class="mw-page-title-main">Bézier curve</span> Curve used in computer graphics and related fields

A Bézier curve is a parametric curve used in computer graphics and related fields. A set of discrete "control points" defines a smooth, continuous curve by means of a formula. Usually the curve is intended to approximate a real-world shape that otherwise has no mathematical representation or whose representation is unknown or too complicated. The Bézier curve is named after French engineer Pierre Bézier (1910–1999), who used it in the 1960s for designing curves for the bodywork of Renault cars. Other uses include the design of computer fonts and animation. Bézier curves can be combined to form a Bézier spline, or generalized to higher dimensions to form Bézier surfaces. The Bézier triangle is a special case of the latter.

In mathematics, the determinant is a scalar value that is a function of the entries of a square matrix. The determinant of a matrix A is commonly denoted det(A), det A, or |A|. Its value characterizes some properties of the matrix and the linear map represented by the matrix. In particular, the determinant is nonzero if and only if the matrix is invertible and the linear map represented by the matrix is an isomorphism. The determinant of a product of matrices is the product of their determinants (which follows directly from the above properties).

<span class="mw-page-title-main">B-spline</span> Spline function

In the mathematical subfield of numerical analysis, a B-spline or basis spline is a spline function that has minimal support with respect to a given degree, smoothness, and domain partition. Any spline function of given degree can be expressed as a linear combination of B-splines of that degree. Cardinal B-splines have knots that are equidistant from each other. B-splines can be used for curve-fitting and numerical differentiation of experimental data.

<span class="mw-page-title-main">Vector space</span> Algebraic structure in linear algebra

In mathematics and physics, a vector space is a set whose elements, often called vectors, may be added together and multiplied ("scaled") by numbers called scalars. Scalars are often real numbers, but can be complex numbers or, more generally, elements of any field. The operations of vector addition and scalar multiplication must satisfy certain requirements, called vector axioms. Real vector space and complex vector space are kinds of vector spaces based on different kinds of scalars: real coordinate space or complex coordinate space.

In linear algebra, the Cholesky decomposition or Cholesky factorization is a decomposition of a Hermitian, positive-definite matrix into the product of a lower triangular matrix and its conjugate transpose, which is useful for efficient numerical solutions, e.g., Monte Carlo simulations. It was discovered by André-Louis Cholesky for real matrices, and posthumously published in 1924. When it is applicable, the Cholesky decomposition is roughly twice as efficient as the LU decomposition for solving systems of linear equations.

<span class="mw-page-title-main">Singular value decomposition</span> Matrix decomposition

In linear algebra, the singular value decomposition (SVD) is a factorization of a real or complex matrix. It generalizes the eigendecomposition of a square normal matrix with an orthonormal eigenbasis to any matrix. It is related to the polar decomposition.

<span class="mw-page-title-main">Runge's phenomenon</span> Failure of convergence in interpolation

In the mathematical field of numerical analysis, Runge's phenomenon is a problem of oscillation at the edges of an interval that occurs when using polynomial interpolation with polynomials of high degree over a set of equispaced interpolation points. It was discovered by Carl David Tolmé Runge (1901) when exploring the behavior of errors when using polynomial interpolation to approximate certain functions. The discovery shows that going to higher degrees does not always improve accuracy. The phenomenon is similar to the Gibbs phenomenon in Fourier series approximations.

<span class="mw-page-title-main">Composite Bézier curve</span> Geometric shape

In geometric modelling and in computer graphics, a composite Bézier curve or Bézier spline is a spline made out of Bézier curves that is at least continuous. In other words, a composite Bézier curve is a series of Bézier curves joined end to end where the last point of one curve coincides with the starting point of the next curve. Depending on the application, additional smoothness requirements may be added.

In linear algebra, an n-by-n square matrix A is called invertible, if there exists an n-by-n square matrix B such that

Bézier surfaces are a species of mathematical spline used in computer graphics, computer-aided design, and finite element modeling. As with Bézier curves, a Bézier surface is defined by a set of control points. Similar to interpolation in many respects, a key difference is that the surface does not, in general, pass through the central control points; rather, it is "stretched" toward them as though each were an attractive force. They are visually intuitive and, for many applications, mathematically convenient.

<span class="mw-page-title-main">Non-uniform rational B-spline</span> Method of representing curves and surfaces in computer graphics

Non-uniform rational basis spline (NURBS) is a mathematical model using basis splines (B-splines) that is commonly used in computer graphics for representing curves and surfaces. It offers great flexibility and precision for handling both analytic and modeled shapes. It is a type of curve modeling, as opposed to polygonal modeling or digital sculpting. NURBS curves are commonly used in computer-aided design (CAD), manufacturing (CAM), and engineering (CAE). They are part of numerous industry-wide standards, such as IGES, STEP, ACIS, and PHIGS. Tools for creating and editing NURBS surfaces are found in various 3D graphics and animation software packages.

In mathematics, the spectral radius of a square matrix is the maximum of the absolute values of its eigenvalues. More generally, the spectral radius of a bounded linear operator is the supremum of the absolute values of the elements of its spectrum. The spectral radius is often denoted by ρ(·).

<span class="mw-page-title-main">Spline (mathematics)</span> Mathematical function defined piecewise by polynomials

In mathematics, a spline is a special function defined piecewise by polynomials. In interpolating problems, spline interpolation is often preferred to polynomial interpolation because it yields similar results, even when using low degree polynomials, while avoiding Runge's phenomenon for higher degrees.

In the mathematical field of numerical analysis, De Casteljau's algorithm is a recursive method to evaluate polynomials in Bernstein form or Bézier curves, named after its inventor Paul de Casteljau. De Casteljau's algorithm can also be used to split a single Bézier curve into two Bézier curves at an arbitrary parameter value.

In mathematics, a totally positive matrix is a square matrix in which all the minors are positive: that is, the determinant of every square submatrix is a positive number. A totally positive matrix has all entries positive, so it is also a positive matrix; and it has all principal minors positive. A symmetric totally positive matrix is therefore also positive-definite. A totally non-negative matrix is defined similarly, except that all the minors must be non-negative. Some authors use "totally positive" to include all totally non-negative matrices.

<span class="mw-page-title-main">Polygonal chain</span> Connected series of line segments

In geometry, a polygonal chain is a connected series of line segments. More formally, a polygonal chain is a curve specified by a sequence of points called its vertices. The curve itself consists of the line segments connecting the consecutive vertices.

<span class="mw-page-title-main">Euclidean plane</span> Geometric model of the planar projection of the physical universe

In mathematics, a Euclidean plane is a Euclidean space of dimension two, denoted E2. It is a geometric space in which two real numbers are required to determine the position of each point. It is an affine space, which includes in particular the concept of parallel lines. It has also metrical properties induced by a distance, which allows to define circles, and angle measurement.

<span class="mw-page-title-main">Matrix (mathematics)</span> Array of numbers

In mathematics, a matrix is a rectangular array or table of numbers, symbols, or expressions, arranged in rows and columns, which is used to represent a mathematical object or a property of such an object.

In mathematics, the Schoenflies problem or Schoenflies theorem, of geometric topology is a sharpening of the Jordan curve theorem by Arthur Schoenflies. For Jordan curves in the plane it is often referred to as the Jordan–Schoenflies theorem.

References

  1. Rida T. Farouki (2007), "Variation-diminishing Property", Pythagorean-Hodograph Curves: Algebra and Geometry Inseparable, Springer, p. 298, ISBN   9783540733973
  2. Schoenberg, I. J.. “Über variationsvermindernde lineare Transformationen.” Mathematische Zeitschrift 32 (1930): 321-328.
  3. T. N. T. Goodman (1999), "Shape properties of normalized totally positive bases", Shape Preserving Representations in Computer-Aided Geometric Design, Nova Publishers, p. 62, ISBN   9781560726913
  4. Farin, Gerald (1997). Curves and surfaces for computer-aided geometric design (4 ed.). Elsevier Science & Technology Books. ISBN   978-0-12-249054-5.