Symmetry and Bivariate Splines

Year: 2012 Authors: Tatyana Sorokina

Core claim

Symmetric partitions tend to yield higher-dimensional spline spaces than asymmetric ones for the spline families studied.

Topics

bivariate splines, symmetry, dimension of spline spaces, planar tessellations

Domains

multivariate spline theory, polynomial spaces, triangulations, dimension formulas, tiling patterns, geometric design, computer-aided geometric design

Methods

theorem-based analysis, dimension comparison, case study of partitions, proof by contradiction

Media

planar tessellations, triangular and quadrilateral partitions, Figure 1-5 diagrams

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2012: Mathematics, Music, Art, Architecture, Culture

Symmetry and Bivariate Splines

Tatyana Sorokina

Mathematics Department

Towson University

8000 York Road

Towson, MD, 21252, USA

E-mail: tsorokina@towson.edu

Abstract

Bivariate splines are piecewise polynomials in two variables defined over planar tessellations. Most of these tessellations are symmetric in some sense and represent famous design and tiling patterns. We show that this symmetry is an intrinsic property of bivariate splines directly related to the concept of dimension of spline spaces.

1. Introduction

A bivariate spline is a function which is made up of pieces of polynomials in two variables defined on a partition $Δ$ of a polygonal domain $Ω$ in the plane. These pieces are joined together to ensure some order $r$ of global smoothness. Bivariate splines are highly effective tools in numerical analysis, computer-aided geometric design and image analysis. A detailed mathematical treatment of bivariate splines can be found in [1]. The vast majority of partitions used in applications appear symmetric in some sense. Moreover, they are composed of famous design and tiling patterns, see all three patterns in Figure 1, and the symmetric versions in Figures 2, 3, 4 on the left. However, in many applications, this symmetry is not

Figure 1: Patterns often appearing as partitions for bivariate splines.

desirable, since the scattered data does not come on the grid. Why do researchers use semi-regular symmetric patterns then? In this paper we show that viable spline spaces tend to favor symmetric partitions. When defined on a finite partition, bivariate splines are linear spaces with finite dimension. Viable spline spaces have low degree of polynomial pieces, high smoothness, and high dimensions. The high dimension is needed to accommodate the available for modeling data. For many important spline spaces, the dimensions are not known. The main reason appears to be the dependency of the dimension on the exact geometry of the partition, see [2] for more details. In particular, dimensions seem to depend on symmetry of the partition. We shall refer to symmetry in a broad sense, since in most cases defining the exact dependency is an open question. For example, smooth quadratic splines over the middle pattern in Figure 1 absorb the three non-regular edges, yielding the pattern on the left. The pattern on the right is the less applicable than the one on the left. The results of this paper suggest that symmetry of the partition accommodates higher dimensions of spline spaces, which in turn provides more flexibility for modeling.

Sorokina

2. Smooth Splines and Symmetry

In this paper, the elements of the partition $Δ$ are triangles and quadrilaterals. We first introduce the space of splines as follows:

S_{d}^{'} (Δ) = {s \in C^{'} (Ω), s ∣_{T} \in P^{d}, f or a llT \in Δ},

where $P^{d}$ is the space of polynomials in two variables of total degree $\leq d$ . Some smooth splines of degree $d \leq 4 r + 1$ are known to show strong dependency on the geometry of the underlying triangulation. In general, not much is known about spaces of splines of degree $d \leq 3 r + 1$ . It is believed that their dimension always depends on the geometry of the partition. In this section, we investigate two families of smooth spline spaces and their dimensions.

Figure 2 shows two partitions of a quadrilateral. Both partitions consist of four triangles, thus, they are called four-cells. The split on the left is symmetric about the point $O$ , while the one on the right is not.

Figure 2: Symmetric (left) and asymmetric (right) four-cells.

The following two theorems show that for a fixed degree and smoothness, the dimension of splines on a symmetric four-cell is higher than that on an asymmetric one. The proofs follow from Theorem 9.3 in [1].

Theorem 2.1. The dimensions of polynomial splines of degree $d$ and positive smoothness $r \leq d$ on the symmetric four-cell depicted in Figure 2 (left) are given by the following formulas:

dim S_{d}^{'} (Δ_{sy m}) = 2 d^{2} + 3 r^{2} - 4 d r + 2 d + 1, i f d \geq 2 r,

\dim S _ {d} ^ {\prime} \left(\Delta_ {s y m}\right) = \frac {3}{2} d ^ {2} + r ^ {2} - 2 d r + \frac {5}{2} d - r + 1, \quad i f d &lt; 2 r.

Theorem 2.2. The dimensions of polynomial splines of degree $d$ and positive smoothness $r \leq d$ on the asymmetric four-cell depicted in Figure 2 (right) are given by the following formulas:

dim S_{d}^{'} (Δ_{a sy m}) = dim S_{d}^{'} (Δ_{sy m}) - δ, w h e r e δ = (d - r + 1 2), i f d \leq r + ⌊ \frac{r}{2} ⌋ δ = \frac{1}{2} (1 + ⌊ \frac{r + 1}{2} ⌋ + 2 d - r) (d - r - ⌊ \frac{r}{2} ⌋) - \frac{1}{2} ⌊ \frac{r}{2} ⌋ ⌊ \frac{r + 2}{2} ⌋, i f r + ⌊ \frac{r}{2} ⌋ δ = ⌊ \frac{r + 1}{2} ⌋ ⌊ \frac{r + 2}{2} ⌋, i f d \geq 2 r . lt; d lt; 2 r,

Figure 3 shows two partitions of a triangle. Both consist of seven triangles. They are known as Morgan-Scott triangulations. The split on the left is symmetric about each of the three lines formed by the pairs of points $(u, U)$ , $(ν, V)$ and $(w, W)$ . The split on the right is not symmetric in the following sense: the three points of pairwise intersections of the lines $(u, U)$ , $(ν, V)$ and $(w, W)$ are not collinear. We note

Symmetry and Bivariate Splines

here that this asymmetry can be specified more, however, it is still on open question to what extent. The following two theorems show that for a fixed degree that equals to a double of smoothness, the dimension of splines on a symmetric Morgan-Scott triangulation is one higher than that on an asymmetric one. The proofs follow from Theorems 1 and 2 in [3].

Figure 3: Symmetric (left) and asymmetric (right) Morgan-Scott splits.

Theorem 2.3. The dimensions of polynomial splines of degree $d = 2 r$ on the symmetric and asymmetric Morgan-Scott split in Figure 3 are given by the following formulas, respectively:

dim S_{2 r}^{r} (Δ_{s y m}) = (2 2 r + 2) + 3 q (r - q) - 3 (2 q + 1) + 1, w h e r e q = ⌊ \frac{r}{3} ⌋,

dim S_{2 r}^{r} (Δ_{a s y m}) = dim S_{2 r}^{r} (Δ_{s y m}) - 1.

3. Continuous Splines and Symmetry

Dimensions of continuous splines (with $r = 0$ ) on triangulations have no dependency on symmetry, see Chapter 9 in [1]. There is not much known about continuous splines over arbitrary partitions. In this section we study spline spaces over a partition consisting of triangles and quadrilaterals. These spaces manifest dependency on the geometry of the underlying partition.

Figure 4 shows two partitions of a triangle. Both partitions consist of one triangle and three quadrilaterals. We shall call them mixed splits. The split on the left is symmetric in the following sense: the three lines formed by the pairs of points $(u, U)$ , $(ν, V)$ and $(w, W)$ are concurrent. The split on the right does not have this property. The following theorem shows that the dimension of linear continuous splines on the symmetric mixed split is one higher than that on the asymmetric one. The proof follows from Proposition 3.1 in [4]. However, that proof uses complicated machinery from Algebraic Geometry, and the paper is still unpublished. We show below a different proof based on a simple geometric argument.

Figure 4: Symmetric (left) and asymmetric (right) mixed splits.

Sorokina

Theorem 3.1. The dimension of polynomial splines of degree $d = 1$ and smoothness $r = 0$ on the symmetric mixed split in Figure 4 (left) is equal to four, while it is three on the asymmetric one in Figure 4 (right).

Proof. We first show that in order to interpolate a piecewise linear continuous function $f$ over the symmetric split, exactly four pieces of data are needed. The three values $f (u), f (v)$ and $f (w)$ define a linear piece over the triangle $[u, v, w]$ . Let $O$ be the point of the intersection of the three lines $(u, U), (v, V)$ and $(w, W)$ , see Figure 5 (left). Then the triple ${f (O), f (u), f (v)}$ uniquely defines the linear piece over the triangle $[O, U, V]$ , and thus, over the quadrilateral $[U, V, v, u]$ . Similarly, the triple ${f (O), f (u), f (w)}$ uniquely defines the linear piece over the triangle $[O, U, W]$ , and thus, over the quadrilateral $[U, W, w, u]$ . Finally, the triple ${f (O), f (v), f (w)}$ uniquely defines the linear piece over the triangle $[O, V, W]$ , and thus, over the quadrilateral $[V, W, w, v]$ . In fact, the spline can be visualized as a truncated tetrahedron with the base $[f (U), f (V), f (W)]$ and the truncated vertex $f (O)$ that is cut off with the triangle $[f (u), f (v), f (w)]$ . The spline is continuous since its values on the segments $[u, U], [v, V], [w, W]$ are uniquely defined by the pairs of values ${f (O), f (u)}, {f (O), f (v)}$ , and ${f (O), f (w)}$ , respectively. This proves the first assertion of the statement of the theorem.

We now consider the asymmetric mixed split, and we will show that four pieces of data overdetermine the spline. The three values $f (u) = 0$ , $f (v) = 0$ and $f (w) = 1$ define a linear piece over the triangle $[u, v, w]$ . Let $O$ be the point of the intersection of the two lines $(u, U)$ and $(v, V)$ , see Figure 5 (right), and let $f (O) = 0$ . Then the values $f (O) = 0$ , $f (u) = 0$ , $f (v) = 0$ make the linear piece over the quadrilateral $[U, V, v, u]$ to be identically equal to zero. The linear piece over the quadrilateral $[U, W, w, u]$

Figure 5: Proof of Theorem 3.1. The edge $[v, w]$ is removed on the right for clarity.

is then defined by $f (O) = 0$ , $f (u) = 0$ , $f (w) = 1$ , while the linear piece on $[V, W, w, v]$ is determined by $f (O) = 0$ , $f (v) = 0$ , $f (w) = 1$ . We now show that this spline is not continuous on the line $(w, W)$ . Let $P$ be the point of intersection of the lines $(u, O)$ and $(w, W)$ . Both of these lines belong to the plane of the linear piece over $[U, W, w, u]$ . Since $f (O) = f (u) = 0$ , the value $f (P)$ must be zero. We next define $Q$ as the point of intersection of the lines $(v, O)$ and $(w, W)$ . Both of these lines belong to the plane of the linear piece over $[V, W, w, v]$ . Since $f (O) = f (v) = 0$ , the value $f (Q)$ must be zero. Thus, we have $f (P) = f (Q) = 0$ . But the point $w$ lies on the line $(P, Q)$ . Therefore, $f (w) = 0 \neq = 1$ , which is a contradiction. It follows that the spline is uniquely determined by three values $f (u)$ , $f (v)$ and $f (w)$ . Moreover, this spline is simply a plane.

References

[1] M. J. Lai and L. L. Schumaker, Spline Functions on Triangulations, Cambridge University Press, Cambridge. 2007. [2] T. Sorokina, Intrinsic Supersmoothness of Multivariate Splines, Numerische Mathematik, Vol. 116, pp. 421-434. 2010. [3] D. Diener, Instability in the Dimension of Spaces of Bivariate Piecewise Polynomials of Degree 2r and Smoothness Order r, SIAM Journal of Numerical Analysis, Vol. 2, pp. 543-551. 1990. [4] Z. Luo, An Invariant of Algebraic Curves from the Pascal Theorem, arXiv:1201.1344v1 [math AG], pp. 1-15. 2012.

Jusur / Bridges Research Atlas

Explorer

Symmetry and Bivariate Splines

Symmetry and Bivariate Splines

Core claim

Topics

Domains

Methods

Media

Paper text

Symmetry and Bivariate Splines

Abstract

1. Introduction

2. Smooth Splines and Symmetry

3. Continuous Splines and Symmetry

References