Page 185 - Geometric Modeling and Algebraic Geometry

10 Cube Decompositions 187
can also be studied with the use of a real eigenbasis. However, we believe that it
is much more difficult to detect and classify them without a geometrically intuitive
decomposition of the initial input.

Fig. 10.3. Polygons can be added as vectors. The orientation of each polygon is shown by the
arrow inside it. Notice that if the sum of two regular coplanar polygons does not degenerate,
then it has the same orientation as the component with the larger norm.

The polygonal decomposition we studied above corresponds to a small part of
the subdivision mesh, that is, a face or the 1-ring neighborhood of a vertex. To obtain
results related to higher order properties of the limit surface, we have to study de-
compositions of larger pieces of the subdivision mesh. The main technical difficulty
in constructing such decompositions is that the corresponding matrices are circulant
block rather than circulant. In [8], decompositions of larger areas of a subdivision
mesh are studied in the context of the Catmull-Clark scheme.

10.3 G-circulant matrices

A matrix is called G-circulant if each row is obtained from the first row by a per-
mutation by an element of a group G, and the rows and columns of the matrix are
indexed by the elements of G. If the group G = Z n is cyclic, then we obtain the
usual circulant matrices.
First we give some background theorems which allow the computation of the
eigenvalues and eigenvectors of a G-circulant matrix, where G is a finite abelian
n
group. Notice that the groups Z and Z 2 ×Z n we are interested in, are finite abelian.
2
Proposition 1. Let G be a finite abelian group. Let the first row of the G-circulant
matrix S be (a g ) g∈G . Then, the eigenvalues of S are given by

λ χ = χ(g)a g (10.10)
g∈G