Beiträge zur Algebra und Geometrie Contributions to Algebra and Geometry Volume 35 (1994), No. 2, 259-281.

Spaces of Stresses, Projections and Parallel Drawings for Spherical Polyhedra

Henry Crapo* and Walter Whiteley†

Bât 9, INRIA, B.P. 105 78153 Le Chesnay, Cedex France** Departement of Mathematics and Statistics, York University 4700 Keele St, North York, Ontario, M3J-1P3 Canada‡

Abstract. Our first paper [1] analyzed the basic three way connection among static self stresses of plane frameworks, reciprocal diagrams and spatial oriented polyhedra. We extend this pattern to describe new:

(i) isomorphisms between (a) the affine space of polyhedra with a fixed projection;

(b) the vector space of self stresses of the framework; and

(c) the space of reciprocal figures of the framework (with one fixed vertex); (ii) and dually, appropriate maps between

(d) the vector space of parallel drawings of spatial polyhedral surfaces,

(e) the space of frameworks with a fixed reciprocal, and

(f) the space of parallel drawings (infinitesimal motions) of the projections.

1. Introduction

Building on the fundamental insights of James Clerk Maxwell for spherical polyhedra and planar graphs [4], our paper [1] presented the equivalence, for plane drawings of 3-connected planar graphs, of the following three properties: the existence of

(i) a self stress on the drawing (as a bar framework), non-zero on all edges;

* Work supported, in part, by a grant from N.S.E.R.C. (Canada)

† Work supported, in part, by grants from N.S.E.R.C. (Canada) and F.C.A.C. (Canada) and F.C.A.C. (Quebec) ** also: École d’architecture Université de Montréal, C.P. 6128 succursale A, Montreal, Quebec, H3C-3J7 Canada, e-mail: crapo@ inria.inria.fr

‡ also: C.R.M. Université de Montréal, C.P. 6128 succursale A, Montreal, Quebec, H3C-3J7 Canada, e-mail: whiteley@mathstat.yorku.ca

0138-4821/93 $ 2.50 \begin{matrix}c \\ ◯ \end{matrix}1994 Heldermann Verlag, Berlin

260 H.Crapo and W.Whiteley: Spaces of Stresses, Projections and Parallel Drawings

(ii) a reciprocal diagram on the dual planar graph, with dual edges of non-zero length,

perpendicular to the original edges; (iii) a spatial polyhedron, with distinct plane faces at each edge; projecting orthogonally

onto the plane drawing; (iv) a spatial polyhedron on the dual graph, projecting to a reciprocal framework.

Figure 1.1

In this paper, we extend these correspondences to the full vector spaces of self stresses, of reciprocals, and of spatial liftings of a plane drawing. To create these spaces, we need to include degenerate situations (Figure 1.2), where some scalars of the self stress become zero (Figure 1.2A), several points coincide (Figures 1.2C,D), or several faces go coplanar (Figure 1.2B). For these degeneracies, we use a broader definition of a drawing (or framework) - a “2-frame” - where edges are assigned a direction vector, and the two vertices are allowed to coincide in the plane. This more abstract structure provides a natural setting for the study of the space of all self stresses on a planar graph, and permits a simpler and more comprehensive description of the relationships among self stresses, reciprocals, parallel drawings and spatial polyhedral surfaces (Sections 3, 4 and 5).

These isomorphisms are bridges between several areas of current geometric research. They arise both in the study of plane frameworks and in the study of polyhedral pictures. These isomorphisms also have a dual form. They connect the space of infinitesimal motions (parallel drawings) of a framework, the space of frameworks with a fixed reciprocal, and the space of parallel drawings of a spatial polyhedron with this projection. Such parallel drawings of polyhedra are central tools to study Minkowski decompositions of the polyhedra [6, 7, 11]; to study the independence of dihedral angles of polyhedra [15,17], and to study area-preserving maps of cell complexes in 3-space [8].

Our construction of ‘Maxwell reciprocals’ has an essentially Euclidian form. There are also affine variants on this theme, due to Cremona, obtained by rotating our reciprocal by 90^{∘} in the plane. Recent work on combined directions and length constraints in CAD [16] has introduced a reciprocal for more general sets of constraints which incorporates both the Maxwell reciprocals (for directions) and the Cremona reciprocals (for lengths) as special

Figure 1.2

cases. In this extension, the reciprocal pair of plane drawings is no longer associated with some object in 3-space.

Our paper [14] presents a new projective form of the reciprocal - as the cross-section of the spatial polyhedron. (This projective construction reflects the projective invariance of the spaces.)

However the Euclidean form, originating with James Clerk Maxwell has both intuitive content and makes the connection with parallel drawings of polyhedra (another projective property).

In a further paper [2], we will investigate the appropriate generalizations of these vector space results to non-spherical polyhedral surfaces. Important analogs of these results exist for projections of oriented 4-polytopes, for 3dimensional reciprocals, and for 2-stresses in spatial complexes. Partial analogs also hold for self-stresses in the related framework (1-skeleton). These are presented in a separate paper [3].

Acknowledgements. These results are grew out of a long term collaboration with Janos Baracs, within the Structural Topology Research Group at the Université de Montréal. Over a period of years, this group traced the engineering theory of reciprocals back to its flowering in the last century and reconstructed the theory in a modern form.

2. 2-Frames

In our first paper [1], we ruled out degenerate configurations in which two ends of an edge of the graph are placed at the same point, or in which two ‘different’ edges of the graph share the same pair of vertices (or, dually, in which two edges separate the same pair of faces). This restriction was not essential to the proofs – but permitted us to use the usual vocabulary of ‘frameworks’ and ‘graphs’. The essential pattern becomes clearer if we modify our definitions to encompass degenerate figures. Since our basic objects of study are polyhedral surfaces, and their projections, we begin with a revised combinatorics of spatial polyhedra.

2.1. The Combinatorial Polyhedra

In our previous paper, we presented an abstract ‘polyhedral surface’ (Figure 2.1A) by means of a set of diamond shaped ‘edge patches’ (Figure 2.1B). These oriented patches are then matched up (Figure 2.1C), along their ‘edges’ (incident pairs of faces and vertices) to form the overall oriented surface without boundary. For convenience in notation, the revised definitions use the ‘oriented edge patches’ of a spherical combinatorial polyhedron (see below). The two labels ⟨h, i; j, k⟩ and ⟨i, h; k, j⟩ refer to the same oriented patch, with different perspectives (Figure 2.1D).

Figure 2.1

We emphasize the following changes to our previous definitions of ‘polyhedra’:

(i) we allow face and vertex cycles to have length two (or more), and

(ii) we do not insist that the second vertices of the oriented edge patches (edges) in a vertex cycle are distinct (or that the second faces of the edge patches in a face cycle are distinct).

Definition 2.1. A combinatorial spherical polyhedron is a finite set of vertices (abstract points) V = {a_{1}, ..., a_{m}}, a finite set of faces F = {F^{1}, ..., F^{n}}, and a finite (non empty) set of edge patches \underline{E}, such that

(i) edge patches are ordered quadruples of indices e = ⟨h, i; j, k⟩, where h,i refer to distinct vertices and j,k refer to distinct faces;

(ii) if e = ⟨h, i; j, k⟩ is in \underline{E} , then the companion edge patch −e = ⟨i, h; k, j⟩ is in \underline{E} but

⟨h, i; k, j⟩ and ⟨i, h; j, k⟩ are not in \underline{E}; (iii) for each vertex a_{0}, all the edge patches in \underline{E} with first vertex a_{0} form a cycle:

⟨0,i_{s}; j_{s},k_{s}⟩ 1 ≤ s ≤ t (t ≥ 2); with k_{s} = j_{s+1} and j_{t} = k_{1}, and all the edge patches are distinct;

(iv) for each face F^{0}, all the edge patches in \underline{E} with first face F^{0} form a cycle: ⟨h_{s}, i_{s}; 0, k_{s}⟩

1 ≤ s ≤ t (t ≥ 2); with i_{s} = h_{s+1} and i_{t} = h_{1}, and all the edge patches are distinct;

(v) for each pair of vertices a_{0}, a_{m} there is a connecting vertex-edge path: a sequence of patches in \underline{E}, e_{r} = ⟨h_{r}, i_{r}; j_{r}, k_{r}⟩ 0 ≤ r ≤ t, such that h_{r+1} = i_{r} and h_{0} = a_{0}, i_{t} = a_{m};

(vi) for each pair of faces F^{0}, F^{m}, there is a connecting face-edge path: a sequence of

patches e_{s} = ⟨h_{s}, i_{s}; j_{s}, k_{s}⟩ 1 ≤ s ≤ t, such that j_{s+1} = k_{s}, j_{0} = F^{0}, k_{t} = F^{m}; (vii) each simple vertex-edge cycle (closed path) separates the faces into two face-edge path

connected components.

Remark 2.2. The conditions (i) to (vi) of this definition are a series of properties of an oriented homology manifold [5]. These conditions are not independent, but we have listed them for convenience in the proof. Condition (vii) implies this has first homology H_{1} = 0, so the manifold is an homology sphere.

If we associate the pair of edge patches ⟨h, i; j, k⟩ and ⟨i, h; k, j⟩ with an oriented topological disk with a quadrilateral boundary cycle (h, j, i, k) = (i, k, h, j) (Figure 2.1D), the combinatorial spherical polyhedron forms a topological sphere. If E is the set with identified companion pairs in \underline{E}, the combinatorial polyhedron satisfies Euler’s formula for a topological sphere: 2|V | − 2|E| + 2|F | = 4.

Throughout this paper we work with this topology (homology) of the combinatorial polyhedron to define cycles etc.

Remark 2.3. This class of combinatorial spherical polyhedra is closed under duality, an operation which interchanges vertices and faces. If we switch the pairs in each edge patch: sending e = ⟨h, i; j, k⟩ to e^{∗} = ⟨j, k; h, i⟩, the set of oriented edge patches \underline{E} goes into \underline{E}^{∗}. The dual combinatorial polyhedron with ‘vertices’ V^{∗} = F, ‘faces’ F^{∗} = V, and edge patches \underline{E}^{∗}, now satisfies the Definition 2.1. Property (i) is self dual, properties (iii), (v) are dual to (iv), (vi). That (vii) is self-dual is a theorem of combinatorial topology (or duality in homology).

Throughout this paper we speak of duality in this specific combinatorial sense.

Example 2.4. Consider the ‘polyhedron’ illustrated in Figure 2.2A. (This can be visualized, in 3-space, as a tetrahedron with a ‘bite’ out of one edge.) Figure 2.2B redraws the basic graph and labels the vertices and faces. Figure 2.2C shows the set of edge patches (the two outer polygonal edges are identified). Notice that two edge patches have the same

Figure 2.2

Figure 2.3.

pair of faces: ⟨3, 5; C, D⟩, ⟨4, 6; C, D⟩. When we draw the graph of the dual (Figure 2.2D) we create a multigraph – with two edges joining C,D.

When we identify each companion pair of edge patches in \underline{E}, as a single edge in a set E, we create a multigraph (V; E) from the spherical combinatorial polyhedron (V, F; \underline{E}). The dual spherical combinatorial polyhedron gives the dual multigraph (F; E^{∗}). Figure 2.3 illustrates another dual pair of multigraphs (A, B) that satisfy these definitions. (Shaded arrows indicate labels for the ‘back faces’.)

2.2. 2-frames: Stresses and Parallel Drawings

We work with two different realizations of combinatorial spherical polyhedra. First we examine plane realizations of the underlying multigraph, with positions for the vertices and directions for the edges. We call these 2-frames. Then we will look at spatial realizations, with planes for the faces, and points for the vertices: that is spherical polyhedral surfaces (section 4).

Of course, our final objective is to describe the connections between the two realizations – the projections of a spatial realization of the combinatorial polyhedron into the plane, creating 2-frames, and the liftings of a plane 2-frame into a spatial polyhedral polyhedral surface (Section 5).

Definition 2.5. A spherical 2-frame H = ((V, F; \underline{E}); p, d) is a combinatorial spherical polyhedron (V, F; \underline{E}), together with points p: V → R^{2}, p: i → p_{i}, and directions d: \underline{E} → R^{2}, d: e → d_{e}, such that

(i) for each companion pair of edge patches d_{e} = −d_{−e} ≠ 0 (ii) if e = ⟨a, b; j, k⟩ joins vertices a and b, p_{a} − p_{b} = α_{e}d_{e}. (Note that p_{a} − p_{b} could be 0).

The planar frameworks of our first paper [1] (with associated ‘faces’) are 2-frames, if we assign the directed edge e=(a,b) the vector d_{e} = p_{a} − p_{b}. We now define the appropriate analogs (generalizations) of self stresses and infinitesimal motions. For convenience, we will shorten the proper engineering term ‘self stress’ to stress for the duration of this paper.

Definition 2.6. A stress on a 2-frame H = ((V, F, \underline{E}); p, d) is an assignment of scalars ω_{e} to the edge patches such that ω_{e} = ω_{−e} and for each vertex a:

∑_{e} ω_{e}d_{e} = 0 (sum over e ∈ \underline{E} with first vertex a).

A stress is non-trivial if some ω_{e}d_{e} ≠ 0 (equivalently, ω_{e} ≠ 0), and full if all ω_{e}d_{e} ≠ 0. A 2-frame with only the trivial stress is independent.

Since the stresses are the solutions to a system of 2|V | homogeneous linear equations (∑_{e} ω_{e}d_{e} = 0), in the |E| variables ω_{e}, they form a first vector space.

From the definition, the stress satisfies two sets of equations at each vertex:

(i) the vector condition (two linear equations with scalar coordinates): ∑_{e} ω_{e}d_{e} = 0 (sum over e ∈ \underline{E} with first vertex i).

(ii) the moment condition (one scalar equation):

∑_{e} ω_{e}d_{e} × p_{i} = ∑_{e} ω_{e}m_{e} = (0, 0, ∑_{e} ω_{e}m_{e}) = 0

(sum over e ∈ \underline{E} with first vertex i).

Equation (ii) is just equation (i) ×p_{i}, where the ‘cross product’ is taken in the sense of 3-space and the plane vectors have added third component 0. For an edge patch e = ⟨h, i; j, k⟩ and a 2-frame, the turning moment is defined as m_{e} = d_{e} × p_{i}.

These equations also apply to the edge patches of all face-edge cycles. The proof is identical to the proof of Theorem 2.4 in [1], noting that a general cycle in a spherical combinatorial polyhedron is the sum of the vertex cycles in some component.

Proposition 2.1. For any face-edge cycle of the combinatorial spherical polyhedron with edge patches N = {…, e_{i},…}, and any stress on a 2-frame on the graph:

∑_{e_{i}∈N} ω_{e_{i}}d_{e_{i}} = 0 and ∑_{e_{i}∈N} ω_{e_{i}}d_{e_{i}} × a_{i} = 0.

Dual to the stresses (in the sense of linear algebra) are the parallel drawings of the 2-frame. These are vectors p′_{i} for the vertices p_{i} such that (p′_{h} −p′_{i}) is parallel to d_{e} or equivalently, d_{e}^{⊥}·(p′_{h} − p′_{i}) = 0. (d^{⊥} denotes the vector d turned 90^{∘} counterclockwise.)

Definition 2.7. A parallel drawing of a spherical 2-frame H = ((V, F; \underline{E}), p, d) is a second 2-frame H′ = ((V, F; \underline{E}), p′, d) with the same directions.

Since parallel drawing are the solutions of a system of |E| homogeneous linear equations d_{e}^{⊥}·(p′_{h} − p′_{i}) = 0, in the 2|V | variables p′_{i}, we have a second vector space. The two equations for a companion pair of edge patches are redundant:

d_{−e}^{⊥}·(p′_{i} − p′_{h}) = −d_{e}^{⊥}·(p′_{i} − p′_{h}) = d_{e}^{⊥}·(p′_{h} − p′_{i}).

Every 2-frame has a 2-dimensional subspace of trivial parallel drawings, with p′_{i} = c for some fixed point c (Figure 2.4A,B). In our figures, we will only indicate the vector d_{e} when the two vertices are not distinct.

Another standard type of parallel drawing is a dilation p′_{i} = α(p_{i} − r), for some fixed center r, and scalar α (Figure 2.4C). If all the joints of the original 2-frame lie at one point, or the scalar α = 0, the dilation will be trivial (Figure 2.4D,E). The dilations and the translations (p′_{i} = p_{i} − t) (‘dilations towards infinity’ Figure 2.4F) form a subspace generated by the initial 2-frame and the trivial drawings. Figure 2.4G shows a parallel drawing which is not in this space. (With two adjacent vertices fixed, and a change for other vertices, it cannot be a dilation or translation.) Remark 2.8. If we replace the points p′_{i} by their changes u_{i} = p′_{i} − p_{i}, we have a second assignment satisfying the same equations. Since d_{e}^{⊥}·(p_{h} − p_{i}) = 0, d_{e}^{⊥}·(u_{h} − u_{i}) = 0 if, and only if, d_{e}^{⊥}·[(p_{i} +u_{i})−(p_{j} +u_{j})] = 0. In some settings, these changes have been called the parallel drawings. The two interpretations form a vector space of the same dimension, although the ‘trivial’ drawings would now correspond to the translations.

If we call the assignment {…, u_{i}^{⊥},…} = {…, v_{i},…} the velocities of the points, we have the usual infinitesimal motions of a 2-frame or plane framework (Figure 2.5A,B, C,D) [9,12]. The velocities corresponding to a translation now fit an instantaneous translation in a perpendicular direction. The velocities corresponding to the dilations correspond to the usual rotations of a framework about the center of the dilation. We concentrate on the parallel drawings because they relate directly to reciprocal diagrams and to spatial polyhedra.

Remark 2.9. The spaces of stresses and of parallel drawings depend only on the directions d_{e}. Thus, the space of parallel drawings H′′ of a parallel drawing H′, is the same as the space of parallel drawings of the original H.

Moreover, if two 2-frames H, H′ on the same polyhedron have parallel directions, d_{e} = α_{e}d′_{e} (α_{e} ≠ 0) for all edge patches, they also have isomorphic spaces of stresses and

Figure 2.4

Figure 2.5.

parallel drawings. We say H and H′ are parallel. If they also have the same points, then H and H′ are equivalent. (The only differences are the magnitudes of the d_{e}.) We will effectively be working with these equivalence classes of 2-frames throughout this paper.

In our previous papers, [8,9,12], we ignored the selection of joints p_{i}, and called the directed graph with the assignment of lines in the plane (triples) d a 2-frame.

Remark 2.10. For a framework (in the plane) the stresses and the infinitesimal motions are the row and column dependencies of a single rigidity matrix, which has |E| rows and 2|V | columns. The row and column ranks of this matrix give an equation connecting the dimensions of these spaces. This generalizes immediately to the 2-frames.

Corollary 2.2. For a 2-frame H = ((V, F; \underline{E}); p, d) the spaces of stresses and the space of of parallel drawings satisfy the equation:

|E| − dim(stresses(H)) = 2|V | − dim(parallel drawings(H))

Proof. For any matrix:

rank of matrix = # rows – dim(row dependencies)

= # columns – dim(column dependencies)

For the rigidity matrix, which is |E| × 2|V |, the row dependencies are the stresses and the column dependencies are (isomorphisc to) the parallel redrawings. These substitutions give the required equation.

3. Reciprocal 2-frames

We are now ready to define the reciprocal figures for a 2-frame.

3.1. Plane Reciprocals

Definition 3.1. A reciprocal 2-frame of a spherical 2-frame H = ((V, F; \underline{E}); p, d) is a 2frame H^{∗} = ((F, V; \underline{E}^{∗}); P, D) on the dual combinatorial polyhedron, such that for each edge patch e, D^{e^{∗}} = d_{e}^{⊥}.

Figure 3.1

Every 2-frame has reciprocals, since we can place all the points P^{j} at the same spot, with D^{e^{∗}} = (d_{e})^{⊥} (Figure 3.1A,B). We call this a trivial reciprocal. Any other reciprocal is non-trivial (Figure 3.1C). Since the essential idea of a reciprocal will be the orthogonal directions for the edge patch and its dual, we could choose any equivalent set of directions, and create an equivalent set of reciprocals. We choose D^{e^{∗}} = (d_{e})^{⊥} just to guarantee a unique representative of the class of equivalent 2-frames. Figure 2.3 showed another pair of reciprocal 2-frames.

Remark 3.2. Any parallel drawing H^{∗}′ of a reciprocal 2-frame H^{∗} will also be a reciprocal to the same original. The set of all reciprocals of H forms the same vector space as the space of parallel drawings of any fixed reciprocal (even the trivial reciprocal, say, with all vertices at (0, 0)).

Theorem 3.1. For a spherical 2-frame H = ((V, F; \underline{E}); p, d) the following are equivalent, for a given e = ⟨h, i; j, k⟩ ∈ \underline{E}:

(i) the 2-frame has a non-trivial stress with ω_{e}d_{e} ≠ 0; (ii) there is a non-trivial reciprocal 2-frame, with P^{j} ≠ P^{k}; (iii) each trivial reciprocal 2-frame has a non-trivial parallel drawing, with P^{j} ≠ P^{k}.

Proof. (i) ⇔ (ii). Assume that there is a non-trivial stress on the 2-frame. We choose an initial point P^{0} for face F^{0}. For other faces the reciprocal point is defined by for P^{1} = P^{0} + (∑_{e} ω_{e}v_{e})^{⊥} (sum over edge patches dual path from F^{0} to F^{1}). Given any two paths between F^{0} and F^{1}, we get the same value for P^{1}, since the sum up one path and back the other follows a face-edge cycle and gives 0. This completes the reciprocal, which has P^{j} − P^{k} = (ω_{e}d_{e})^{⊥} for each e = ⟨h, i; j, k⟩. This reciprocal is non-trivial, since some P^{j} − P^{k} = (ω_{e}d_{e})^{⊥} ≠ 0.

Conversely, given a non-trivial reciprocal, we can reverse this construction, solving (ω_{e}d_{e})^{⊥} = P^{j} − P^{k} for ω_{e}, to recreate the unique corresponding stress in the original 2-frame.

(ii)⇔ (iii). Since a parallel drawing of a reciprocal is also a reciprocal, this is immediate.

The original 2-frame H for a reciprocal 2-frame H^{∗} is also a reciprocal of H^{∗}, except that d_{e}^{⊥⊥} = −d_{e}. (We should say, ‘the original is equivalent to the reciprocal of the reciprocal’. We will suppress this essentially trivial detail.) Thus the original 2-frame defines a stress in its reciprocal. The frames H, H^{∗} play equivalent geometric roles. Given a reciprocal pair of 2-frames, each defines a stress in the other, so we speak of the mutually defined reciprocal stresses in the reciprocal 2-frames.

By Theorem 3.1, a full stress (non zero on every edge patch) will create a reciprocal 2-frame with the vertices of each edge distinct (Figure 3.2B). However, any other stress, with some edge patch coefficients zero, will create a 2-frame with corresponding pairs of vertices coincident (Figure 3.2C). In particular, the zero stress (all coefficients zero) will correspond to a trivial reciprocal (Figure 3.2D).

3.2. The Isomorphism for Reciprocals and Stresses

Of course, the correspondence of Theorem 3.1 is not unique: the translation of any reciprocal (adding a trivial reciprocal) will correspond to the same stress. If we fix the initial dual point P^{0} at (0, 0), we select an appropriate subspace of reciprocals and a corresponding space of parallel drawings.

Corollary 3.2. For any spherical 2-frame H = ((V, F; \underline{E}), p, d), there are linear isomorphisms between:

Figure 3.2

(i) the space of stresses of the spherical 2-frame; (ii) the subspace of reciprocal 2-frames with P^{0} = (0, 0); (iii) the subspace of parallel drawings of any reciprocal, with P^{0} = (0, 0).

Corollary 3.3. For any spherical 2-frame H = ((V, F; \underline{E}), p, d), with a reciprocal 2-frame H^{∗} = ((F, V; \underline{E}^{∗}), P, D), the following equations hold:

dim(stresses(H)) − dim(stresses(H^{∗}))

= dim(parallel drawings(H^{∗})) − dim(parallel drawings(H))

= |F | − |V | = |E| − (2|V | − 2)

Proof. From Corollary 3.2, we know that:

dim(stresses(H)) = dim(parallel drawings(H^{∗})) − 2, dim(stresses(H^{∗})) = dim(parallel drawings(H)) − 2.

Subtracting these two equations yields the first equality.

From Corollary 2.2, we know also that

|E| − dim(stresses(H)) = 2|V | − dim(parallel drawings(H)). Substituting from our first equation, we have

dim(stresses(H)) − dim(stresses(H^{∗})) = |E| − 2|V | + 2. Finally, by Euler’s Formula

|V | − |E| + |F | = 2 implies |E| − 2|V | + 2 = (|V | + |F | − 2) − 2|V | + 2 = |F | − |V |. This yields the final equality.

4. Spherical Polyhedral Surfaces: Projections and Liftings

In Maxwell’s basic construction, one projects a spatial polyhedron to a plane framework in a plane T and constructs lines normal to the planes (through a fixed center c) intersecting the plane T to form the vertices for a reciprocal framework (Figure 4.1).

To keep ‘frameworks’ (distinct vertices) for these projections and sections, we previously insisted that the spatial vertices of an edge are assigned distinct points, and that

Figure 4.1

the two faces at an edge are assigned distinct planes in 3-space. Allowing 2-frames for the original drawing and the reciprocal, we can remove these restrictions and work with a full vector space of polyhedra.

4.1. Polyhedral Surfaces in 3-space

Definition 4.1. A spherical polyhedral surface is a combinatorial spherical polyhedron, (V, F; \underline{E}), with an assignment q of points q_{i} ∈ R^{3} to the vertices a_{i} and an assignment Q of non-vertical planes Q^{j} = (A^{j}, B^{j}, 1, C^{j}) in 3-space to the faces F^{j} such that if the vertex v_{i} and the face F^{j} share an edge patch then q_{i} is on the plane Q^{j}: A^{j}x_{i}+B^{j}y_{i}+z_{i}+C^{j} = 0.

We note that our definitions permit polyhedral surfaces in which all faces and vertices lie on the same line (Figure 4.2B,C), or all faces have the same non-vertical plane (Figure 4.2A) and the vertices are placed arbitrarily, or dually, all vertices are the same point, and all faces pass through this point (Figure 4.2C).

We want to study the projections of these polyhedral surfaces, as 2-frames. Accordingly, we will need a well-defined ‘direction’ for each edge patch of the spatial polyhedral surface:

(i) Define w′_{e} = q_{h} − q_{j}. If the vertices of an edge patch e = ⟨h, i; j, k⟩ are distinct, this gives a (non-zero) direction for the edge patch.

(ii) Define w′′_{e} = (A^{j}, B^{j}, 1)×(A^{k}, B^{k}, 1) = (B^{j} −B^{k}, A^{k} −A^{j}, A^{j}B^{k} −A^{k}B^{j}) = N^{j} ×N^{k}. If the vertices are not distinct, but the faces are distinct, this gives a non-zero direction for the edge patch.

Figure 4.2

(iii) If the two points coincide, and the two planes coincide, then we choose a vector w′′′_{e}

in the common plane, (with w′′′_{−e} = −w′′′_{e}) as the direction of the edge patch. (Notice that if both the vertices and planes are distinct, these two vectors w′_{e} and w′′_{e} are parallel and non-zero.) We now select a direction w_{e} for each edge patch, using:

w_{e} = α_{e}w′_{e} if this is non-zero;

w_{e} = α_{e}w′′_{e} if this is non-zero but w′_{e} = 0; and
w_{e} = α_{e}w′′′_{e} otherwise;

(α_{e} non-zero, but the same for e and −e). We have ensured that w_{−e} = −w_{e} in all cases, but the length of this vector is an arbitrary choice. This creates the augmented spherical polyhedral surface S = ((V, F; \underline{E}); q, Q, w).

Of course, we have equivalent augmentations (different choices of the scalars α for the edges). In general, we will choose the augmentation to project to the directions of a given plane 2-frame.

4.2. Vertical Projections of Polyhedral Surfaces

Definition 4.2. A 2-frame contains the vertical projection of an augmented spherical polyhedral surface ((V, F; \underline{E}); q, Q, w) if the 2-frame has joints p_{i} = (x_{i}, y_{i}) when q_{i} = (x_{i}, y_{i}, z_{i}), and, for each edge patch ⟨h, i; j, k⟩, d_{e} = (u_{e}, v_{e}) where w_{e} = (u_{e}, v_{e}, w_{e}) (Figure 4.2A).

A face diagram of an augmented spherical polyhedral surface ((V, F; \underline{E}); q, Q, w), Q^{j} = (A^{j}, B^{j}, 1, C^{j}), is a plane 2-frame on the dual combinatorial polyhedron with P^{j} = (A^{j}, B^{j}) for F^{j} and with D^{e} = d_{e}^{⊥} = (u_{e}, v_{e})^{⊥} (Figure 4.1B).

Proposition 4.1. For an augmented spherical polyhedral surface S = ((V, F; \underline{E}); q, Q, w) the vertical projection and the face diagram are reciprocal 2-frames.

Proof. With the given definitions, what we need to prove is that the vertical projection and the face diagram are 2-frames. That is, we must show that the defined d_{e} is parallel to p_{h} − p_{i}, and D^{e^{∗}} is parallel to P^{j} − P^{k}.

From our definition of w_{e}, if the points are distinct, w_{e} = α(q_{h} − q_{i}), so d_{e} = α(p_{h} − p_{i}), as required. If the points are not distinct, then any selected d_{e} will work. Thus the projection is a 2-frame.

If the points and the planes are distinct, w_{e} = q_{h} − q_{i} is parallel to (A^{j}, B^{j}, 1) × (A^{k}, B^{k}, 1) = (B^{j} − B^{k}, A^{k} − A^{j}, A^{j}B^{k} − A^{k}B^{j}). Therefore D^{e^{∗}} = d_{e}^{⊥} is parallel to (A^{j} − A^{k}, B^{j} − B^{k}), as required. If the points are not distinct, but the planes are, we have D^{e^{∗}} = d_{e}^{⊥} = (A^{j} − A^{k}, B^{j} − B^{k}). Finally, if the planes are not distinct, the reciprocal points coincide and any selected value will do. Thus the face diagram is also a 2-frame.

The original 2-frame and the reciprocal form a reciprocal pair with reciprocal stresses. Similarly, given the spherical polyhedral surface projecting to one 2-frame, we can reverse the roles and find a dual spherical polyhedral surface projecting to the reciprocal, with its face normals creating the original. In 3-space, this ‘duality’ is expressed as a projective polarity. Throughout this paper, polarity will refer to the special spatial polar given in the next definition.

Definition 4.3. The Maxwell polarity in space is the pair of transformations L and L^{−1} between points in R^{3} and non-vertical planes defined by L(x, y, z) = (x, y, 1, z) and L^{−1}(A, B, 1, C) = (A, B, C).

Remark 4.4. The Maxwell polarity is a standard projective polarity in 3-space, about the paraboloid x^{2} + y^{2} + 2z = 0. (This is the equation of the points which lie on their polar planes.) We recall that a Euclidean point p = (x, y, z) has projective coordinates (x, y, z, 1). The polarity effectively switches the last two projective coordinates. (Projective points at infinity, (x, y, z, 0), are transformed to vertical planes (x, y, 0, z).)

This (and any) projective polarity takes a point on a plane to a polar plane through the polar point. Thus the polarity takes a spatial polyhedral surface to a dual polyhedral surface. We also recall that the polar of a polar is the original polyhedral surface.

It is not evident what happens to the augmentation. This problem arises because we have written the augmentation w_{e} as a ‘3-vector’ (point at infinity in projective space) when it really is a projective line of intersection (a 6-vector of Plücker coordinates) which would polarize in a coherent fashion. Accordingly, we will polarize the underlying polyhedral surface, and then we augment the result with w^{e^{∗}} so that the chosen w^{e^{∗}} projects to be the projection of w_{e}, turned 90^{∘}.

Proposition 4.2. For an augmented spherical polyhedral surface S = ((V, F; \underline{E}); q, Q, w) and the augmented polar spherical polyhedral surface S^{∗} = ((F, V; \underline{E}^{∗}); L(q), L^{−1}(Q), w^{∗}):

(i) the vertical projection of S is the face diagram of S^{∗}; (ii) the face diagram of S is the vertical projection of S^{∗}.

Proof. For a point q_{i} = (x_{i}, y_{i}, z_{i}), L(x_{i}, y_{i}, z_{i}) = (x_{i}, y_{i}, 1, z_{i}) and the face diagram of S^{∗} uses the point (x_{i}, y_{i}) as does the projection of S. It remains to check that w^{e^{∗}} projects to be d_{e}^{⊥}. If the points or the planes are distinct, our selection of w^{e^{∗}} guarantees this perpendicularity, as in the proof of Proposition 4.1. Otherwise, we made this condition explicit in the choice of w^{e^{∗}}.

Theorem 4.3. For a spherical 2-frame H = ((V, F; \underline{E}); p, d) the following are equivalent, for each edge patch e = ⟨h, i; j, k⟩:

(i) the 2-frame has a stress with ω_{e}d_{e} ≠ 0; (ii) there is a reciprocal 2-frame H^{∗} = ((F, V; \underline{E}^{∗}); P, D) with P^{j} ≠ P^{k}; (iii) the 2-frame contains a vertical projection of an augmented spherical polyhedral surface

((V, F; \underline{E}); q, Q, w) with Q^{j} ≠ Q^{k}; (iv) the reciprocal 2-frame is a face diagram of an augmented spherical polyhedral surface

((V, F; \underline{E}); q, Q, w) with Q^{j} ≠ Q^{k}.

Proof. Theorem 3.1 gives (i) ⇔ (ii).

(i)&(ii) ⇒ (iii),(iv) We will use one stress, in the original, to produce a polyhedral surface over the reciprocal. We then polarize to get the required polyhedral surface over the original.

Choose a vertex F^{0} = (A^{0}, B^{0}) in the reciprocal, and set q^{∗0} = (A^{0}, B^{0}, 0). For each edge patch e = ⟨h, i; j, k⟩ make the 3-vector t_{e} = (ω_{e}d_{e}, 0). Recall that m_{e} = d_{e} × p_{h} = d_{e} × p_{i}. We now define the spatial line segment for an edge patch:

L_{hi} = t_{e} × (x_{h}, y_{h}, 1) = (ω_{e}d_{e}^{⊥}, ω_{e}m_{e}) = (A^{j} − A^{k}, B^{j} − B^{k}, 0) + (0, 0, ω_{e}m_{e}). For every other face F^{1}, there is a vertex-edge path N = {⟨h, i; j, k⟩} from F^{0} to F^{1}.

We set q^{∗1} = q^{∗0} + (∑_{e∈N} L_{hi}) = (A^{0}, B^{0}, 0) + (∑_{e∈N} L_{hi})

= (A^{0}, B^{0}, 0) + ∑_{e∈N}(A^{j} − A^{k}, B^{j} − B^{k}, 0) + ∑_{e∈N}(0, 0, ω_{e}m_{e})
= (A^{1}, B^{1}, 0) + ∑_{e∈N}(0, 0, ω_{e}m_{e}).

Since ∑ ω_{e}m_{e} = 0 on any face-edge cycle, this point is well defined. q^{∗1} clearly projects into the reciprocal point P^{1}.

In addition, all the edges for any vertex v_{h}, (dual face) are formed by lines L_{hi} which are perpendicular to the fixed vector N^{h} = (x_{h}, y_{h}, 1), so they all lie in a plane, with (x_{h}, y_{h}, 1) as normal. The points q^{∗j} and these induced planes give the required polyhedral surface over the reciprocal, with the original 2-frame as the face-diagram. Finally, we can select w^{e^{∗}} to augment the spatial polyhedral surface, choosing w^{e^{∗}} to project onto d_{e}^{⊥}.

(iii) or (iv) ⇒ (i) follows from Proposition 4.1.

4.3. The Isomorphism of Stresses and Liftings

As we run through the space of stresses we create a set of polyhedral surfaces with the same projection. These polyhedral surfaces form an affine space.

Definition 4.5. The vertical liftings of a 2-frame H = ((V, F; \underline{E}); p, d) are the set of all polyhedral surfaces S′ = ((V, F; \underline{E}); q′, Q′, w), with H as the vertical projection.

This set is an affine space. Given two such liftings,

S = ((V, F; \underline{E}); q, Q, w), S′ = ((V, F; \underline{E}); q′, Q′, w),

consider the affine combination

tS + (1 − t)S′ = ((V, F; \underline{E}); tq + (1 − t)q′, tQ + (1 − t)Q′, tw + (1 − t)w). For each vertex v_{i}:

t(x_{i}, y_{i}, z_{i}) + (1 − t)(x_{i}, y_{i}, z′_{i}) = (x_{i}, y_{i}, tz_{i} + (1 − t)z′_{i})

and for each face F^{j}:

t(A^{j}, B^{j}, 1, C^{j}) + (1 − t)(A^{′j}, B^{′j}, 1, C^{′j})
= (tA^{j} + (1 − t)A^{′j}, tB^{j} + (1 − t)B^{′j}, 1, tC^{j} + (1 − t)C^{′j}).

While these points project correctly, it remains to prove that this is a lifting. For each edge patch ⟨h, i; j, k⟩:

[tA^{j} + (1 − t)A^{′j}]x_{i} + [tB^{j} + (1 − t)B^{′j}]y_{i} + [tz_{i} + (1 − t)z′_{i}] + [tC^{j} + (1 − t)C^{′j}]

= t[A^{j}x_{i} + B^{j}y_{i} + z_{i} + C^{j}] + (1 − t)[A^{′j}x_{i} + B^{′j}y_{i} + z′_{i} + C^{′j}] = 0 + 0.

The liftings are an affine space. If we restrict to the liftings with a first face F^{0} at Q^{0} = (0, 0, 1, 0), we have a smaller affine subspace.

(Equivalently, after fixing x_{i}, y_{i}, for the points and 1 as the third coordinate of the planes, we can do the usual vector addition and scalar multiplication on the remaining coordinates:

(x_{i}, y_{i}, z_{i}) ⊕ (x_{i}, y_{i}, z′_{i}) = (x_{i}, y_{i}, z_{i} + z′_{i}); and α(x_{i}, y_{i}, z_{i}) = (x_{i}, y_{i}, αz_{i}); and

(A^{j}, B^{j}, 1, C^{j}) ⊕ (A^{′j}, B^{′j}, 1, C^{′j}) = (A^{j} + A^{′j}, B^{j} + B^{′j}, 1, C^{j} + C^{′j});
α(A^{j}, B^{j}, 1, C^{j}) = (αA^{j}, αB^{j}, 1, αC^{j}).

This will make an equivalent vector space.)

Theorem 4.4. For any spherical 2-frame H = ((V, F; \underline{E}); p, d), there following spaces are isomorphic:

(i) the vector space of stresses of the spherical 2-frame; (ii) the vector space of reciprocals with P^{0} = (0, 0); (iii) the vector space of parallel drawings of a given reciprocal, with P^{′0} = (0, 0); (iv) the affine space of general spherical polyhedral surfaces, with Q^{0} = (0, 0, 1, 0), which

project into the 2-frame.

Proof. It is simple to verify that the constructions given for Theorems 3.1 and 4.3 are linear with respect to the defined vector spaces and the affine space. That they are non-singular follows from the addenda in these theorems that ω_{e} ≠ 0 if and only if P^{j} ≠ P^{k} if and only if P^{′j} ≠ P^{′k} if and only if Q^{j} ≠ Q^{k}.

Figure 4.3 illustrates a selection of corresponding (A,A′, B,B′ etc.) parallel drawings of a reciprocal and projected liftings of the original (light lines indicate coplanar adjacent faces).

Figure 4.3

5. Parallel Redrawings of Polyhedral Surfaces

We have given constructions from a stress in a 2-frame to a reciprocal and two mutually polar polyhedral surfaces in space. These constructions have been interpreted as linear and affine transformations. There is one space which is missing. The polars of the space of liftings of the original form a space of dual augmented polyhedral surfaces projecting to the space of reciprocals. Since all these dual polyhedral surfaces have the same face diagram (the original 2-frame), their faces have the same normals (Figures 1.1, 1.2).

5.1. The Isomorphism of Parallel Drawings in the Plane and 3-Space

Definition 5.1. Given an augmented polyhedral surface S = ((V, F; E); q, Q, w) (with no vertical faces), a parallel drawing is an augmented polyhedral surface S′ = ((V, F; \underline{E}); q′, Q′, w) with faces parallel to the original polyhedral surface: (A^{′j}, B^{′j}, 1) = (A^{j}, B^{j}, 1).

The fact that the augmentation w is unchanged, would automatically force the faces to the same normal, except in the degenerate case where all w_{e} for edge patches of a face were collinear!

The set of parallel drawings forms an affine space. (For the vertices alone it is a vector space, but the normals and edge directions make it affine.) Those parallel drawings with a selected initial vertex q_{0} = (0, 0, 0) form an affine subspace.

Since we are describing the spaces from the perspective of the spatial polyhedral surfaces, two polyhedral surfaces on the same combinatorial polyhedron, with the same projection are called shadow equivalent polyhedral surfaces.

Theorem 5.1. Given a spatial polyhedral surface ((V, F; \underline{E}); q, Q, w) and a spherical 2-frame which is the vertical projection then

(i) the affine subspace of shadow equivalent surfaces of the polyhedral surface (Q^{0} held constant) is isomorphic to the space of stresses of the 2-frame;

(ii) the affine space of parallel drawings of the polyhedral surface (q^{0} held constant) is isomorphic to the subspace of parallel drawings of the 2-frame with p^{0} fixed.

Proof. We have shown part (i) in Theorem 4.4.

(ii) Clearly any orthogonal projection of a parallel drawing of the polyhedral surface is a parallel drawing of the first projection.

Finally, parallel drawings of the projection are reciprocals of the common face diagram for all of the polyhedra. Therefore, by Theorem 4.4, polarized, these lift to augmented polyhedral surfaces with the reciprocal as the face diagram. Since these share the same normals to faces as the original, and their augmentations project to the same directions, these liftings are parallel drawings of the original augmented polyhedral surface.

If we consider a general configuration of lines and points in 3-space, with the natural definition of ‘parallel drawing’, it is clear that a parallel drawing in 3-space always projects to a parallel drawing of the projection. However the converse is false – some plane parallel drawings do not lift to parallel drawings in 3-space. In a future paper we will prove that this lifting of all parallel drawings fails for toroidal polyhedra. Here we give a simple non-polyhedral counterexample to lifting parallel drawings.

Figure 5.1

Example 5.4. Consider a skew quadrilateral in 3-space. This has only trivial parallel drawings – the translations and dilations. (Figure 5.2A illustrates how an attempt at a nontrivial parallel drawing breaks down.) However the plane projection, a plane quadrilateral, always has non-trivial parallel drawings (corresponding to the non-trivial infinitesimal motions of the corresponding quadrilateral framework).

The correspondence for spherical polyhedra immediately translates standard plane results about infinitesimal motions of the projection into theorems about parallel drawings of the spatial polyhedron.

Corollary 5.2. Given a spatial spherical polyhedral surface S = ((V, F; \underline{E}); q, Q, w), with at least two distinct vertices, and a spherical 2-frame H = ((V, F; \underline{E}); p, d) which is the vertical projection of S then the following are equivalent:

(i) the polyhedral surface S has a parallel drawing beyond translation and dilation; (ii) the projected 2-frame H has a parallel drawing beyond translation and dilation; (iii) the projected 2-frame H has an infinitesimal motion beyond translation and rotation.

Proof. The equivalence of (i) and (ii) follows from Theorem 5.1 and the fact that projection takes the trivial parallel drawings of S (a 4-space of translations and dilation) into trivial parallel drawings of H (a 3-space of translations and dilations – with vertical translation in the kernel).

The equivalence of (ii) and (iii) follows from the remarks in Section 3. We know that infinitesimal motions correspond to parallel drawings in the plane. We also know that the ‘trivial’ 3-space of translations and dilations corresponds to the ‘trivial’ 3-space of translations and rotations, provided that there are at least two distinct vertices. (If all vertices coincide, then ‘dilations’ and ‘rotations’ of the 2-frame reduce to translations.)

5.2. Applications of the Parallel Drawing Isomorphism

Parallel drawings in 3-space are important for the study of independence and dependence of angles in spatial configurations, and the study of Minkowski decomposition [6]. Since we know a lot about plane rigidity, and less about these spatial studies, Corollary 5.2 and its relatives are used to transfer results from the plane to higher dimensions. We illustrate this with one example. [7] and [11] give many other examples.

Example 5.5. Consider the 2-frame drawn in Figure 5.2A (the evident regions are the faces). With all vertices distinct, this is a plane framework, with |E| = 14 = 2|V | − 2. Clearly, there is at least a 3-space of parallel drawings (translations and dilations) - so by Corollary 3.3, the space of stresses must have dimension at least 1. This is the vertical projection of some spatial polyhedral surface with two (or more) distinct faces. (Notice that this particular combinatorial spherical polyhedron is self dual.)

A more subtle analysis shows that |E′| ≤ 2|V′| − 3 for all non empty subsets of edges, and a standard result for plane frameworks shows that an open dense subset of all realizations of the graph with distinct vertices has exactly a one dimensional space of stresses (generated by a full stress). It also follows that these 2-frames have only the trivial parallel drawings. We conclude that ‘generic’ drawings (e.g. using algebraically independent

Figure 5.2

coordinates for the vertices) will be the vertical projection of a spatial polyhedral surfaces with all vertices and faces distinct, and that these spatial polyhedral surfaces will have only trivial parallel drawings.

Example 5.6. Some special positions for the framework will have non-trivial parallel drawings (Figure 5.2B). These special configurations will also have a larger space of stresses and liftings in which some pairs of faces are coplanar (the light lines in Figure 5.2C). Notice that when the framework (2-frame) has a larger space of parallel drawings, its reciprocal will also have a larger space, by Corollary 3.3.

At the level of the spatial polyhedron, this demonstrates that when the spatial polyhedron has an extra parallel drawing (for geometric reasons), then its Maxwell polar also has an extra parallel drawing (for polar geometric reasons).

Corollary 5.3. For any augmented spherical polyhedral surface S = ((V, F; \underline{E}); q, Q, w), with polar augmented spherical polyhedral surface S^{∗} = ((F, V; \underline{E}^{∗}); q^{∗}, Q^{∗}, w^{∗}):

dim(parallel drawings(S^{∗})) − dim(parallel drawings(S))

= |F | − |V | = |E| − (2|V | − 2)

Remark 5.7. It is well-known that the dimensions of the spaces of stresses in a framework, and of the space of infinitesimal motions (parallel drawings) are projectively invariant [9,11]. This same result extends immediately to stresses and parallel drawings of any plane 2-frame. Therefore, the isomorphic spaces of liftings and spatial parallel drawings are also isomorphic under projective transformations of the plane framework, or 2-frame.

It is also known that the dimension of the space of parallel drawings of a spatial configuration is projectively invariant. Corollary 5.3 extends from the ‘special’ Maxwell polarity to arbitrary polarities in 3-space.

For a plane 2-frame on a combinatorial spherical polyhedron, this shows that lifting to a spatial polyhedron, doing a projective transformation in 3-space (no face vertical) and reprojecting will not change the dimension of the space of parallel drawings. By Corollary 3.2, this lifting, projective transformation and reprojection will also not change the dimension of the space of stresses. This is a far wider invariance that just projective transformations in the plane.

Remark 5.8. If we take any configuration of planes and points in 3-space, we can define a space of parallel drawings, and a space of projections and liftings. It is a simple observation [13] that for any configuration of planes and points polarity takes the space of parallel drawings of one configuration to the space of ‘shadow equivalent’ configurations of its spatial polar. What is special for spherical polyhedra is the connections between parallel drawings in 3-space and the plane projection.

Remark 5.9. We have presented this Euclidean theory for vertical projections of polyhedral surfaces into the plane. There is a related theory for central projections of polyhedral surfaces onto a sphere (projection from the center of the sphere). It is well-known that statics and infinitesimal kinematics on the surface of a sphere are equivalent (via central projection), to statics and infinitesimal kinematics in the plane [10].

The face diagram becomes the placing of normals on the ‘Gaussian sphere’ – an ‘angle diagram’ which illustrates all of the angles of the original polyhedron. These reciprocal edges remain orthogonal to the original projection, at their crossing point. Most of the spaces we study have direct analogs, although the idea of ‘parallel drawing’ on a sphere, where there are no parallel ‘lines’ (great circles), becomes a more specific idea of ‘share the same reciprocal’. This theory will be presented in [17], where it is used to study the combinatorics and geometry of dihedral angles in polyhedra.

Based on the observed strong transfer of geometric results which hold for spherical and Euclidean geometries to hyperbolic geometry, we anticipate that a comparable theory of reciprocals exists for the hyperbolic plane as well.

References

[1] H. Crapo and W. Whiteley: Plane self stresses and projected polyhedra I: the basic pattern; Structural Topology 20 (1993), 55-78.

[2] H. Crapo and W. Whiteley: Projections, stresses, liftings and reciprocals for toroidal polyhedra; preprint, York University, North York, Ontario, 1993.

[3] H. Crapo and W. Whiteley: 2-Stresses in 3-space and projections of 4-polytopes: reciprocals, liftings and parallel configurations; preprint, York University, North York, Ontario, 1993.

[4] J.C. Maxwel: On reciprocal diagrams and diagrams of forces; Phil. Mag. Series 4, 27 (1864), 250-261.

[5] J.R. Munkres: Elements of Algebraic Topology; (Addison-Wesley, Reading Mass., 1984).

[6] G.C. Shephard: Decomposible convex polyhedra; Mathematika 10 (1963), 89-95.

[7] T-S. Tay: Decomposition of polytopes; preprint, National University of Singapore, Singapore, draft chapter (1987) for: The Geometry of Rigid Structures, H.Crapo and W.Whiteley eds.

[8] T-S. Tay, White,N. and Whiteley,W.: Skeletal rigidity of simplicial complexes I, II; Eur. J. Comb. to appear.

[9] N. White and W. Whiteley: The algebraic geometry of motions in bar and body frameworks; SIAM J. Alg. Disc. Meth. 8 (1987), 1-32.

[10] W. Whiteley: Cones, infinity and 1-story buildings; Structural Topology 8 (1983), 53-70.

[11] W. Whiteley: Parallel redrawings of configurations in 3-space; preprint, York University, North York, Ontario, 1987.

[12] W. Whiteley: The union of matroids and the rigidity of frameworks; SIAM J. Disc. Appl. Math. 1 (1988), 237-255.

[13] W. Whiteley: A matroid on hypergraphs, with applications to scene analysis and geometry; Disc. Comp. Geometry 4 (1988), 75-95.

[14] W. Whiteley: Weavings, sections and projections of spherical polyhedra; Disc. Applied. Math 32 (1991), 275-294.

[15] W. Whiteley: How to describe a polyhedron; to appear in: Journal of Intelligent and Robitic Systems.

[16] W. Whiteley: Constraining plane configurations in CAD: the geometry of direction and lengths constraints; preprint, York University, North York, Ontario, 1994.

[17] W. Whiteley: Determination of spherical polyhedra; to appear.

Received August 2, 1993.