Page 181 - Geometric Modeling and Algebraic Geometry

10 Cube Decompositions 183
of the subdivision matrix, aiming at deriving the local analytic properties of the limit
surface. On the other hand, the focus of this paper is on the explicit decomposition of
the initial shape into simple geometric components corresponding to the eigenvectors
of the subdivision matrix. As we will discuss in section 10.2, such decompositions
can reveal interesting geometric properties of the limit shape which are difficult to
infer from its analytic properties.
One additional factor making the geometric decompositions of the shapes inter-
esting, is that they are not unique. First, the eigenvectors of the matrix usually have
high geometric multiplicity. Then, each eigenvector may be represented by more than
one component of the sum in Eq. 10.1. Indeed, as we will see in section 10.5, the use
of several copies of a geometric eigencomponent, placed in different positions in the
3d space, may lead to more intuitive decompositions of the initial shape.

10.1.2 Previous Work

The transformation of a polygon by joining the middles of adjacent edges to create
a new polygon is simple geometric problem where circulant matrices arise. It was
studied as early as 1878 by Darboux in [1]. Several generalizations of this problem
have been studied and the connection between such transformations and circulant
matrices is now well-understood [2, 3, 4, 5, 6]. Applications of this theory to the
study of subdivision surfaces have been proposed in [7, 8].
Regarding the G-circulant matrices, their spectral properties are usually studied
with the use of group characters. In this paper we keep the standard terminology
and notation of [9], even though we deal with finite abelian groups only, and thus
utilize a very small portion of the theory of group characters. Advanced results on
the relation between G-circulant matrices and graphs can be found in [10], while the
block-diagonalization of G-circulant matrices, where G is non-abelian, is studied in
[11].

10.1.3 Overview

As motivation for the study of higher dimensional objects, in section 10.2 we discuss
decompositions of polygons. In section 10.3 we briefly review the standard termi-
nology from character theory and the basic theorems that allow us to compute the
eigenvalues and eigenvectors of G-circulant matrices, where G is an abelian group.
In section 10.4 we study decompositions of n-dimensional cubes by eigenvectors
of subdivision matrices corresponding to multivariate quadratic splines. Finally, in
section 10.5 we study the decompositions of prisms by the eigenvectors of a sub-
division matrix corresponding to the tensor extension of the Doo-Sabin surface
subdivision scheme.

10.2 Circulant matrices and polygonal decompositions

A matrix is called circulant if each row is the previous row cycled forward one step