The Unit Cube Qⁿ

We abbreviate Qⁿ := [0, 1]ⁿ, i.e. the n-cube. So Qⁿ is all points x = (α₁, ..., α_n) where all α_i ∈ [0, 1]. For this vignette we assume n ≥ 3.

A vertex of Qⁿ is a point where all α_i = 0 or 1; there are 2ⁿ vertices. If two vertices differ by exactly one coordinate, they are the endpoints of an edge, and the “free” coordinate parameterizes the edge. There are n2^n − 1 edges. If four vertices differ by two coordinates, they are the vertices of a square, and the two “free” coordinates parameterize the square. There are $\binom{n}{2} 2^{n-2}$ squares. In the familiar case when n = 3, there are 8 vertices, 12 edges, and 6 squares. Note that (α₁, ..., α_n) ∈ ∂Qⁿ iff some α_i= 0 or 1. Thus vertices, edges, and squares are all subsets of ∂Qⁿ.

The standard involution ρ : Qⁿ → Qⁿ is the map (α₁, ..., α_n) ↦ (1 − α₁, ..., 1 − α_n). It is clear that ρ maps a vertex to an antipodal vertex, Similarly, there are pairs of antipodal edges and antipodal squares. ρ has a unique fixed point (1/2, ..., 1/2), which is the center of symmetry.

The 2-Transition Subcomplex Q₂ⁿ ⊊ Qⁿ

This section treats the 2-transition subcomplex of Qⁿ with n ≥ 3, which we denote by Q₂ⁿ. We define it in three ways.

Definition 1:
Visualize the indexes 1, ..., n as points on the circle, like beads in a necklace, or the n roots of unity. Different points i ≠ j divide the other points into 2 contiguous “arcs” (one of them may be empty). Define (α₁, ..., α_n) ∈ Q₂ⁿ iff there are i ≠ j, so that α_k = 0 for k in one arc and α_k = 1 for k in the other arc.

There are 2 ways to choose 0 and 1, so as α_i and α_j vary, they “sweep out” 2 disjoint and antipodal squares in Qⁿ. The total number of these 2-transition squares is n(n − 1). Q₂ⁿ is the union of these squares, joined along their edges.

It is helpful to visualize points in the unit cube as bar graphs. Here are four points in Q₂¹⁰, with 2 transitions:

mybarplot <- function( x )  {
n = length(x)
plot( c(0,n), c(0,1), type='n', tcl=0, las=1, xaxt='n', xlab='', ylab='', mgp=c(3,0.25,0) )
grid( nx=NA, ny=NULL, lty=1 )
barplot( x, names.arg=1:n, space=0, add=T, yaxt='n', mgp=c(3,0.25,0) )
}

x1 = numeric(10) ; x1[ c(3,8) ] = exp( c(-0.25,-1) ) ; x1[ 4:7 ] = 1
x2 = numeric(10) ; x2[ c(5,6) ] = exp( c(-1,-0.25) )

oldpar = par( mfrow=c(2,2)  , omi=c(0,0,0,0), mai=c(0.45,0.5,0.1,0) )
mybarplot( x1 )   ; mybarplot( x2 )     #  row #1
mybarplot( 1-x1 ) ; mybarplot( 1-x2 )   #  row #2

Figure 2.1 four points in the 2-transition complex, visualized with bar graphs

par( oldpar )

For the first point, the run of 1s has length 4, and the (circular) run of 0s also has length 4. For the next plot, the run of 1s has length 0, and the (circular) run of 1s has length 8. The points in row #2 are derived by applying the involution to the point above it. Of course, the involution turns runs of 1s to runs of 0s, and vice-versa.

The special vertices (0, ..., 0) and (1, ..., 1) are in Q₂ⁿ by this definition, although they technically have no transitions. Also, if α_i = 0 except for one i, that point is also in Q₂ⁿ because it is in an edge of one of the above-defined squares.

Note that Q₂³ = ∂Q³, i.e. every point in the boundary of Q³ is a 2-transition point.

Definition 2:
This definition views a 2-transition point as a special discrete projection of a 2-transition function defined on a circle.

Given n, define n + 1 points, β_i := i + 1/2 for i = 0, ..., n, and n intervals I_i := [β_i − 1, β_i] = [i − 1/2, i + 1/2] for i = 1, ..., n. These intervals have length 1 and are a partition of [1/2, n + 1/2].

Let J₂ be the set of all (step) functions on [β₀, β_n] that take the values 0 or 1 and have two transitions or no transitions (jumps). We identify the endpoints β₀ and β_n to form a circle, so if the functions values at β₀ and β_n are different, then this is considered to be a transition. Equivalently J₂ is the set of all indicator functions 1_A where A is an arc in the circle. We allow the arc to be empty (the function is identically 0), or the entire circle (the function is identically 1). Define a function p() Note that α_i is the mean of f on I_i. So if f is identically 1 on I_i, then α_i = 1 in p(f). And the same is true with 1 replaced by 0. But if f has a jump in I_i, then α_i can be anywhere in [0, 1] depending on where the jump occurs. If there is exactly one jump in I_i, then the location of the jump is uniquely determined by α_i. But if there are two jumps in I_i, then the 2 jump locations are not determined by α_i. It only determines the distance between the jumps, so both can be translated a little bit and not change α_i. Thus, p is not injective.

Here are plots with 2 examples:

mystepplot <- function( x )  {
# assumption: x is Type I
n = length(x)
plot( c(1/2,n+1/2), c(0,1), type='n', tcl=0, las=1, xlab='', ylab='', lab=c(n,5,7), mgp=c(3,0.25,0) )
grid( lty=1 )
beta = seq(1/2,n+1/2,by=1) ; segments( beta, 0, beta, -0.02 )
ij = which( 0<x & x<1)  ;  lambda = ij + c(1/2 - x[ ij[1] ], x[ ij[2] ] - 1/2)
lines( c(0.5,lambda[1]), c(0,0) ) ; lines(lambda,c(1,1)) ; lines( c(lambda[2],n+1/2), c(0,0) )
segments( lambda, c(0,0), lambda, c(1,1), lty=3 )
}

oldpar = par( mfrow=c(2,2), omi=c(0,0,0,0), mai=c(0.45,0.5,0.1,0) )
mystepplot( x1 ) ; mystepplot( x2 )     #  row #1
mybarplot( x1 ) ; mybarplot( x2 )       #  row #2

Figure 2.2

par( oldpar )

The 1st plot shows a function f ∈ J₂ with jumps in intervals I₃ and I₈. The plot below it shows p(f) ∈ Q₂¹⁰. The 2nd plot shows a function f ∈ J₂ with jumps in intervals I₅ and I₆. The plot below it shows p(f) ∈ Q₂¹⁰. In the 1st row, the sequence β_i (all of them half-integers) is marked with small tick marks.

We now define Q₂ⁿ to be the image of p(); i.e. Q₂ⁿ := p(J₂). It is straightforward to show that Definition 2 and Definition 1 are equivalent.

Now we look at J₂ in more detail. Every function in J₂ is integrable, so we can think of J₂ ⊊ L¹(𝕊¹), which is the space of integrable functions on the circle 𝕊¹.

Theorem With the L¹ topology, J₂ is homeomorphic to the 2-sphere 𝕊².

Proof Denote the 2 functions in J₂ that are identically 0 or 1 by f₀ and f₁. For a point in J₂ − {f₀, f₁}, the corresponding arc A is non-trivial, and so the midpoint of the arc is a well-defined point in 𝕊¹. The length of the arc is in the open interval (0, 2π). This assignment gives a homeomorphism from J₂ − {f₀, f₁} to the open cylinder U := 𝕊¹ × (0, 2π). Note that as two points in J₂ get closer to f₀, they get closer to each other in the L¹ metric; and similarly for f₁. So if bottom and top boundaries of U are each collapsed to a point, and f₀ and f₁ are mapped to those two points, it continuously extends the above homeomorphism to all of J₂ and to the cylinder with collapsed boundaries, which is just a 2-sphere 𝕊². ▫

Later, we will see that Q₂ⁿ is also homeomorphic to 𝕊². But the above mapping p : J₂ ↠ Q₂ⁿ is not a homeomorphism, because we observed above that p is not injective.

Definition 3:
This definition works directly with vertices and squares of Qⁿ. A 2-transition vertex is one with a single circular run of 0s, and a single circular run of 1s. A run is allowed to empty, and this yields the vertex of all 0s and all 1s. A 2-transition square is a square whose 4 vertices are all 2-transition vertices. Note that the center of the square has exactly 2 coordinates with value 1/2, and the other values are a circular arc of 0s and an arc of 1s. We now define Q₂ⁿ to be the union of all these 2-transition squares. It is an example of a cubical subcomplex of Qⁿ. Once again, it is straightforward to show that Definition 3 and Definition 1 are equivalent.

For an x := (α₁, ..., α_n) ∈ Q₂ⁿ, we define the level of x be the number of α_i’s that equal 1. The level varies from 0 to n. The level is constant on the interior of an edge and the interior of a square. We define the level of a square to be the level on the interior. The level of a square varies from 0 to n − 2. It is helpful to think of level=0 squares at the “bottom” of the subcomplex, and level=n − 2 squares at the “top”.

So we know that Q₂ⁿ is a union of squares, but what does it “look like”, and what is its topology? We claim that Q₂ⁿ is a 2-sphere 𝕊². In the case of n = 3 this is easy to see, since Q₂³ = ∂Q³.

In general, first consider all the 2-transition squares with level=0. It is straighforward to show that such a square has 0 as a vertex, and it has 2 vertices with level=1 and one vertex with level=2. Each edge from 0 to a level 1 vertex is shared by two of the squares, and so the squares are arranged in circular fashion around 0. Their union is a topological disk 𝔻² at the “bottom”. Similarly, the level=n − 2 squares form a disk at the “top”.

Now consider squares with fixed level 𝓁 with 0 < 𝓁 < n − 2. It is easy to show that in each square, both of the level=𝓁 + 1 vertices are in one other square, so the level 𝓁 squares form a “necklace of n diamonds”. These n − 3 necklaces are stacked on top of each other to form a cylinder, and the cylinder is capped at bottom and top to form the 2-sphere 𝕊². We now verify the square count in Q₂ⁿ; n + n(n − 3) + n = n(n − 1) which is correct.

The following figure is a helpful visualization.

rgl::par3d( zoom=0.7 )
rgl::mfrow3d( 1, 2 )
zono =  polarzonohedron(9)
plot2trans( zono )
rgl::next3d()
plot2trans( zono, level=c(0,4,7) )
rgl::rglwidget( webgl=TRUE )

This figure plots the image of Q₂⁹ in ℝ³ under a suitable linear map. The squares are distorted into parallelograms. The figure on the left draws the full subcomplex, and the one on the right only draws levels 0, 4, and 7. The “necklace of 9 diamonds” at level=4 is easily visible. The black dot is the image of (0, ..., 0), and the white dot is the image of (1, ..., 1).

More about these linear maps is given in the next section.

The 2-Transition Surface S₂ ⊊ Z ⊊ ℝ³

Let the zonohedron Z := L(Qⁿ), where L : ℝⁿ ↠ ℝ³ is a surjective linear map. From now on we assume that Z is pointed, which means that 0 is a vertex of Z.

Let S₂ := L(Q₂ⁿ) be the image of the 2-transition subcomplex Q₂ⁿ. Since the subcomplex is a union of squares glued on the edges to form a 2-sphere 𝕊², S₂ is a union of parallelograms glued on the edges. S₂ is a tesselated surface, but may not be a sphere because it may have self-intersections.

We are mainly interested in the case that there are no self-intersections, and there is a precise way to state this. Let L₂ be the restriction of L to Q₂ⁿ. So L₂ : Q₂ⁿ → ℝ³ is the composition of the inclusion Q₂ⁿ ⊊ ℝⁿ followed by L. The surface has no self-intersections iff L₂ is injective.

For example, in the previous figure S₂ does not have self-intersections and is a topological 2-sphere. L₂ is injective.

If L₂ is injective, then it is well-known ([1], [7] p. 117, and [2] p. 161) that S₂ divides ℝ³ into an inside region and an outside region whose intersection is S₂. Moreover, the inside region is homeomorphic to a closed ball, and S₂ is the boundary of that ball.

Since Q₂ⁿ ⊊ Qⁿ, S₂ = L(Q₂ⁿ) ⊊ L(Qⁿ) = Z. We emphasize that S₂ is a surface, and Z is a solid. We also emphasize that S₂ depends intimately on the order of the generators, and Z does not depend on the order at all.

Polygons

A polygon for us is more than just a subset of the plane. A polygon is a finite and cyclically ordered set of distinct vertices, plus the line segments that connect the vertices in cyclic order. The line segments are called the edges. The union of the edges is a subset of the plane, but two different sets of vertices can generate the same subset - the vertices matter.

A simple polygon is a polygon whose edges do not intersect, except at corresponding endpoints; i.e. the polygon has no self-intersections. By the Jordan Curve Theorem, a simple polygon, as just a set, has an inside region and an outside region, and both are connected. Note that a non-simple polygon may also have a connected inside region; it might “double-back” on itself within an edge, and then proceed forward again.

A convex polygon is a polygon with an inside region that is convex.

There is an equivalent definition of polygon using functions. Let U_n be the set of n’th root of unity on the unit circle in ℂ, plus the edges connecting these vertices in order. So U_n is sort of a quintessential or template polygon. A general polygon is a function f : U_n → ℝ² which is injective on the vertices (the image vertices are distinct) and linear on each edge. Since f is injective on the vertices, it is also injective on each edge; one can think of f as a piecewise-linear immersion of U_n. A polygon defined this way is simple iff f is injective.

This is an unintuitive way to define a polygon, but has the advantage that it generalizes easily to one higher dimension, as we see later in Section 9.

The Generator Polygon P

Since Z is pointed, there is a plane K in ℝ³ that has 0 in one open halfspace, and all the generators of Z in the other open halfspace. This “cutting” hyperplane intersects S₂ in a polygon. Each vertex of the polygon is the intersection of K and the segment from 0 to a generator. The cyclic order of its vertices is inherited from the order of the generators. We call this the generator polygon and let P := K ∩ S₂ denote it.

P may not be a simple polygon in general; it may have self-intersections.

Since there can be many cutting hyperplanes K, P is only defined up to a projective transformation. In colorimetry for example, there are three chromaticity diagrams, from 1931, 1960, and 1976. They are all generator polygons for the same set of generators, and the 3 polygons differ by projective transformations, see [4].

Parallelograms in S₂ and ∂Z

Given ∂Z and S₂ as above, the goal in this section is to show that each is a union of n(n − 1) parallelograms, and to set up a 1-1 correspondence between the parallelograms in S₂ and those in ∂Z. Each parallelogram will also be assigned a unit normal in such a way that corresponding parallelograms have the same normal.

First consider ∂Z. If a facet of Z is not a parallelogram, let it be tiled with the standard tiling by parallelograms, see the Zonotopes vignette. Given an unordered pair {i, j} with 1 ≤ i, j ≤ n and i ≠ j, there are 2 antipodal parallelograms in ∂Z. The edges of both parallelograms are the generators L(e_i) and L(e_j). If 𝒫 is one of those parallelograms, we know that 𝒫 is the image of some square in Qⁿ. The following Lemma algebraically characterizes which squares map to a parallelogram 𝒫 ⊂ ∂Z.

Lemma: Let Σ be a square in Qⁿ. By definition Σ is determined by an unordered pair {i, j} and for all k ∉ {i, j}, an assignment of α_k to either 0 or 1. The coordinates α_i and α_j are ‘free’ in [0,1] and sweep out the square. Let the parallelogram 𝒫 := L(Σ) ⊊ Z be the image of the square. Let w := L(e_i) × L(e_j) be the cross product of the edges of 𝒫. Then 𝒫 ⊂ ∂Z iff for all k ∉ {i, j}

Note that the two conditions are almost the same; the first 2 cases merely swap 0 and 1, and the third case is the same in both conditions. The third case is not really new; it comes from the definition of the square. Also note that the order of i and j affects the definition of w, but if i and j are swapped, w is changed to −w which merely swaps the two conditions.

Proof: Let λ be the linear functional z ↦ ⟨z, w⟩. Since ⟨L(e_i), w⟩ = ⟨L(e_j), w⟩ = 0, the values of α_i and α_j have no effect on λ(L(x)). Similarly, in the last case where ⟨L(e_k), w⟩ = 0, α_k has no effect. This case only happens when L(e_k) is a linear combination of L(e_i) and L(e_j), and the corresponding facet is non-trivial with 6 or more edges. The facet then requires a selected tiling, and different tilings yield different assignments of 0 and 1 to α_k.

If the square Σ satisfies the first condition above, then any x ∈ Σ maximizes λ(L(x)) over all x ∈ Qⁿ. Therefore L(Σ) ⊂ ∂Z, by the definition of Z. If the square Σ satisfies the second condition, then λ(L(x)) is minimized and the conclusion is the same.

Conversely, if the square satisfies neither condition, then λ(L(x)) for x ∈ Σ is strictly between the maximum and the minimum. This means that L(Σ) is in an intermediate hyperplane orthogonal to w. The intersection of an intermediate hyperplane with ∂Z is only a 1-dimensional polygon and cannot contain a parallelogram. Thus L(Σ) ⊄ ∂Z. ▫

Define a slab in ℝ³ to be the region between two parallel planes, including the planes themselves. In equation form, a slab 𝒮 is given by where w ∈ ℝ³ is the non-zero plane normal, and ⟨x, w⟩ = α and ⟨x, w⟩ = β are the two planes. If α < β then each point in the boundary planes of 𝒮 has a unique outward-pointing unit normal. But if α = β then the planes coincide, the slab degenerates to that plane, and a normal cannot be assigned unambiguously.

Given an unordered pair {i, j} with 1 ≤ i, j ≤ n and i ≠ j, there are 2 antipodal parallelograms in ∂Z. The edges of both parallelograms are the generators L(e_i) and L(e_j). They define two distinct parallel planes and therefore a non-degenerate slab denoted by 𝒮^{i, j}. The slab has 2 well defined boundary normals, which we assign to the 2 parallelograms in the boundary of the slab. Note that if u is the unit normal for one of the parallelograms 𝒫, then u is a multiple of the cross product L(e_i) × L(e_j).

Now consider S₂. Given an unordered pair {i, j} as above, there are 2 antipodal parallelograms in S₂ and the edges of both are the generators L(e_i) and L(e_j). These 2 parallelograms are parallel to each other; let 𝒮₂^{i, j} be the slab defined by them. The 2 parallelograms in ∂Z given by {i, j} have the same edges - the generators L(e_i) and L(e_j). So it is clear that 𝒮₂^{i, j} ⊆ 𝒮^{i, j}. If this new slab is non-degenerate, then each of the two parallelograms in S₂ can be matched to exactly one of the two parallelogram in ∂Z by choosing the one with the same normal vector. If this new slab is degenerate, its outward-pointing normal is not defined, and we can pick an assignment at random.

This completes the goal of this section.

An interesting observation: since corresponding parallelograms are congruent, they have the same surface area, and therefore S₂ and ∂Z have the same surface area as well.

A Theorem about S₂ and the Convexity of P

Recall our assumptions that Z has a simple matroid, and is pointed.

1. S₂ = ∂Z
2. L₂ is injective, and the inside region of S₂ is convex
3. P is a simple convex polygon, possibly with collinear vertices

The equivalence of properties 1 and 3 is proved in West & Brill [10], except the sequence of vector generators in this theorem is replaced by a continuous path of vectors in [10]. To our knowledge, property 2 is new.

Proof:
1. ⟹ 2. L₂ is clearly injective on each square. If a parallelogram of S₂ is in ∂Z then it must be the corresponding parallelogram (or its antipodal) in ∂Z from the previous section. This mapping of parallelograms is 1-1, and since the parallelograms of ∂Z are disjoint (except on the edges) the parallelograms of S₂ are disjoint (except on the edges). Therefore L₂ is injective.

The inside region of S₂ is the inside region of ∂Z, which is Z, which is convex.

2. ⟹ 3. (trivial) The polygon P is the intersection of a hyperplane and the boundary of a convex polyhedron, and that intersection is a convex polygon. Since L₂ is injective, P is simple.

3. ⟹ 1. For a generator L(e_i), let v_i be the corresponding vertex of P. It is the intersection of the ray generated by L(e_i) and the cutting hyperplane K. Note that v_i is a positive multiple of L(e_i).

Firstly we show that S₂ ⊆ ∂Z.

Let {i, j} be an unordered pair of indexes as above. These indexes divide the remaining indexes into 2 contiguous circular sequences. Let 𝒫 be one of the corresponding parallelograms of S₂, and let u be its unit normal. By definition, 𝒫 is the image under L of a 2-transition square Σ in Q₂ⁿ. For Σ, all α_k in one sequence are 0, and all α_k in the other sequence are 1.

We want to show that 𝒫 is also in ∂Z. Let ℒ be the line through v_i and v_j. The plane given by ⟨x, u⟩ = 0 contains both L(e_i) and L(e_j), and so ⟨v_i, u⟩ = ⟨v_j, u⟩ = 0. The line ℒ divides K into a positive side and a negative side. For another vertex v_k, ⟨L(e_k), u⟩ > 0 iff v_k is on the positive side of ℒ, and ⟨L(e_k), u⟩ < 0 iff v_k is on the negative side of ℒ.

Consider the relationship between ℒ and P.

Case i). ℒ intersects the interior of P
Since P is convex, all the v_k in one contiguous sequence are on the positive side of ℒ and all the v_k in the other contiguous sequence are on the negative side of ℒ. This implies that all the generators L(e_k) in one contiguous sequence, have ⟨L(e_k), u⟩ > 0, and all the generators L(e_k) in the other contiguous sequence have ⟨L(e_k), u⟩ < 0. But we saw earlier that the α_k in one sequence are all 0, and the α_k in the other sequence are all 1. This is exactly the condition given by the Lemma in the previous section. Therefore 𝒫 ⊆ ∂Z.

Case ii). ℒ intersects ∂P, but not the interior of P
This case is a little more subtle, but basically the same. Since P is convex, w.l.o.g. we can assume all v_k are either on ℒ or on the negative side of ℒ. Those on the negative side are part of contiguous sequence, so for all these k, α_k is either 0 or 1. For the v_k that are on the line, ⟨L(e_k), u⟩ = 0, so the conditions in the above Lemma do not care whether α_k is 0 or 1. Thus all α_k satisfy the conditions of the Lemma and so 𝒫 ⊂ ∂Z.

Secondly we show that ∂Z ⊆ S₂.

Let 𝒫 ⊂ ∂Z and let Σ be the square whose image is 𝒫. We want to show that every x ∈ Σ has 2-transitions.

Case i). ℒ intersects the interior of P
Then for k ∉ {i, j}, all the generators L(e_k) in one contiguous sequence have ⟨L(e_k), u⟩ > 0, and all the generators L(e_k) in the other contiguous sequence have ⟨L(e_k), u⟩ < 0. In no case is ⟨L(e_k), u⟩ = 0. The Lemma then forces two possibilities for α_k, and both of them have 2 transitions.

Case ii). ℒ intersects ∂P, but not the interior of P
We know v_i and v_j are on the line ℒ. Let ℐ := { l : v_l ∈ ℒ }. Since P is simple, the set of v_l for l ∈ ℐ is contiguous in P.

If i and j are the only indexes in ℐ, then since P is simple and convex, all the other v_k are contiguous and on one side of ℒ. So by the Lemma, for all the other v_k either α_k = 0 or α_k = 1. Therefore every x ∈ Σ has 2 transitions.

If ℐ has more than i and j then the generators L(e_l) for l ∈ ℐ generate a non-trivial zonogon facet of Z. Recall that this facet is tiled with the standard tiling. Since Z is pointed, the zonogon facet is also pointed. And since P is simple, the generators of the facet are in angular order. By the property of the standard tiling in the Zonotopes vignette, we know that there are 2 transitions in the sequence of α_l for l ∈ ℐ. Assume now that all vertices of the complementary sequence are on the negative side of ℒ, so all the complementary α_k = 0. When combined with the α_l, the result is a 2-transition sequence, for every x ∈ Σ. If all vertices of the complementary sequence are on the positive side of ℒ, then we can use the central symmetry of Z to show that the sequence for x is the reflection, and thus still has 2 transitions. ▫

Strictly Starshaped Surfaces

raytrace2trans() is one of the important functions in the package zonohedra. It expects that the 2-transition surface is nice enough so that a given ray intersects the surface in a unique point. This section explores the mathematics of this situation. It is convenient to deal with abstract polyhedral surfaces in ℝ³.

Let S be a polyhedral 2-sphere, i.e. a sphere 𝕊² that is tesselated by polygons, and let f : S → ℝ³ be a continuous map that is injective and linear on each polygon. One can think of f as a piecewise-linear immersion. It may not be injective on all S, so the surface f(S) may have self-intersections. f(S) is a polyhedral surface in ℝ³. We call the surface polygons of f(S) facets. Since S is orientable, we can choose a normal vector n_i for each facet, so that these normals are consistent across the edges. A facet and its normal defines a positive halfspace for the facet, and a negative halfspace for the facet.

The example we have in mind is the 2-transition surface S₂ associated with a zonohedron.

Given the vectors n_i and a point p ∉ f(S) the linking number of p and f(S) is defined as follows. Choose a ray based at p and not intersecting any edge of f(S); this is always possible. Now examine every intersection of the ray with the interior of a facet. If the ray crosses with the same orientation as n_i, assign a +1; otherwise assign a -1. The linking number is defined to be the sum of all these +1s and -1s. It is independent of the chosen ray. Reversing the sign of every n_i yields a consistent vector field and changes the sign of the linking number. The linking number is a straightforward generalization of the winding number of a closed polygonal curve in the plane and a point not on the curve. The linking number is the degree of a certain projection map (sometimes called the Gauss map or linking map) that depends on p and f(S). For more on this subject, see [6] p 53 and [9] p. 296.

Suppose now that f : S → ℝ³ is injective. It is well-known ([1], [7] p. 117, and [2] p. 161) that f(S) divides ℝ³ into an inside region and an outside region whose intersection is f(S). Moreover, the inside region is homeomorphic to a closed ball, and f(S) is the boundary of that ball.

Definition: Let B ⊆ ℝ³ be a closed set and b₀ ∈ B. Then B is starshaped at b₀ iff for any b ∈ B the segment [b₀, b] ⊆ B.

Definition: Let B ⊆ ℝ³ be a closed set with interior and b₀ ∈ int (B). Then B is strictly starshaped at b₀ iff for any b ∈ B the half-open segment [b₀, b) ⊆ int (B).

So to be strictly starshaped, the segment [b₀, b] cannot intersect ∂B except possibly at b.

We now want to extend the concept of strictly starshaped from bodies B to surfaces f(S).

Definition: Let f : S → ℝ³ be as above, and p ∉ f(S). Then f(S) is strictly starshaped at p iff f is injective and the inside region B is strictly starshaped at p.

Note that this definition forces p to be in the interior of B.

1. f(S) is strictly starshaped at p
2. f is injective, and every ray based at p intersects f(S) in exactly one point
3. the linking number of f(S) and p is +1 (resp. -1) and p is in the negative (resp. positive) open halfspace of every facet of f(S)

raytrace2trans() is one of the important functions in the package zonohedra. For the function to work well, we want Property b to be true for the 2-transition surface S₂, but its truth or falsity is not readily computable. However, Property c. is easily computed, and if the surface fails the test, then raytrace2trans() issues a warning that the computed ray intersection may not be unique.

Higher-Transition Points in the Cube Qⁿ

In Section 2, the 2-transition subcomplex Q₂ⁿ ⊊ Qⁿ was defined; it is the subset of points with 2 transitions. We now want to define the number of transitions for any point x ∈ Qⁿ.

When defining the subcomplex Q₂ⁿ above, Definition 2 used the set J₂ of all (step) functions on [β₀, β_n] that take the values 0 or 1 and have two transitions or no transitions (jumps). Let J_∞ be the bigger set of all (step) functions on [β₀, β_n] that take the values 0 or 1 and have a finite number of transitions. The endpoints β₀ and β_n are identified, to form a circle. Equivalently, J_∞ is the set of all indicator functions 1_A⁺ where A⁺ is a finite disjoint union of arcs in the circle. The symbol ∞ does not mean that there can be infinitely many transitions; it means that the transition count is finite but can be arbitrarily large. The transition count is twice the number of arcs, so for any f ∈ J_∞ the transition count of f is a well-defined even integer.

We now want to define the transition count of x ∈ Qⁿ using the function p : J_∞ ↠ Qⁿ, which is defined exactly as in Section 2.

Definition: For any x ∈ Qⁿ define

By this definition, all x ∈ Q₂ⁿ have 2 or 0 transitions. But if x ∉ Q₂ⁿ then x has more than 2 transitions. Following [3], we say that x is a higher-transition point.

Given an x ∈ Qⁿ, the transition count of x is easily computable. In the interval [0,1] the endpoints 0 and 1 are boundary values, and all other values are interior values.

First consider the case when all coordinate values of x are 0 or 1, so x is a vertex. The maximum transition count is when 0 and 1 alternate. A little consideration of small n yields the following table of counts.

At the other extreme is when all coordinate values are interior values, so x is an interior point. A little consideration of small n shows that one can make x = p(f) when f has transition counts in this table:

Finally, consider the general x ∈ Qⁿ. Find all runs of interior values, and the 2 border values on either side of the run. These 2 border values are either equal or not equal. Let r be the length of a run and look up the # of transitions for this specific run in this table:

The numbers in the header row are the possible lengths of the run of interior values. For example, if the length of the run is 1, and the border values are equal the transition count for this sequence is 2. Take the sum of these counts over all runs of interior values. Next, strip out all interior values completely, to leave a circular sequence of 0s and 1s. Compute the number of transitions of this “stripped” sequence in the usual way, and add to the previous sum. This final sum is the transition count for any x ∈ Qⁿ. This shows that p : J_∞ ↠ Qⁿ truly is surjective.

We are mostly interested in the case when L(x) ∈ ∂Z, and then x has at most 2 interior values and the length of a run of interior values is either 1 or 2. From the above algorithm it is clear that for a fixed parallelogram 𝒫 ⊂ ∂Z, and for any x that maps to the interior of 𝒫, the transition count of x is a constant. Thus we can write about the transition count for any parallelogram 𝒫 ⊂ ∂Z.

Given indexes i and j of generators of Z, the transition count for the corresponding parallelogram(s) in ∂Z is fairly easy to compute. The algorithm is in the proof of the theorem in section 7. Let ℒ be the line through vertices v_i and v_j in the generator polygon P. Then then transition count is the number of times that ℒ cuts P. This algorithm is also present in [10].

Parallelograms in S₂ and ∂Z, revisited

By the previous theorem, if the generator polygon P is not simple and convex, then S₂ ≠ ∂Z. This means there is a parallelogram in S₂ that is in the interior of Z.

Let {i, j} be an unordered pair of indexes for such a parallelogram. Consider the slabs 𝒮^{i, j} and 𝒮₂^{i, j} defined above. For simplicity, drop the {i, j} to get just 𝒮 and 𝒮₂.

Since this parallelogram in S₂ is in the interior of the slab, the functional defining the slabs is not maximized on the parallelogram, so we call it deficient. The difference between the functional values on the two parallelograms is called the deficit. The corresponding parallelogram in ∂Z is called abundant because every z in this parallelogram is the image under L of a higher-transition x ∈ Qⁿ. To summarize, each deficient parallogram in S₂ has a matching abundant parallelogram in ∂Z. This is illustrated in the left side of the next figure. The bold line segments correspond to the parallelograms and their antipodals. The outward-pointing normals define the functionals to be maximized. The 2 slabs are labeled. Note 𝒮₂ is a proper subset of 𝒮; in symbols 𝒮₂ ⊊ 𝒮.

Figure 10.1

On the other hand, if a parallelogram of S₂ is in the boundary of the slab 𝒮, then the two parallelograms are equal and we call them coincident. It means that every z in this parallelogram is the image of an x ∈ Qⁿ that has 2 (or 0) transitions. This is illustrated in the right side of the above figure.

To get data about the abundant and coincident parallelograms in ∂Z, use the functions transitionsdf(), for example:

matgen = colorimetry.genlist[[2]]   # the CIE 1931 CMFs at 1nm step
matgen = 100 * matgen / sum( matgen[2, ] )   # it's traditional to scale so the center has Y=50
zono =  zonohedron( matgen )
getcenter(zono) ; dim( getmatrix( getsimplified( getmatroid(zono) ) ) )

##        x        y        z 
## 50.00400 50.00000 50.01653

## [1]   3 340

transitionsdf( zono )

##        transitions parallelograms     area.min     area.max   area.sum   deficit.min   deficit.max   example
## 1                2          93360 7.114460e-09 2.003446e+00 33110.4010 -1.776357e-13  1.563194e-13 {446,587}
## 2                4          12770 2.296428e-10 6.361879e-01   542.5573  9.426770e-11  2.071725e+00 {558,606}
## 3                6           6570 4.248782e-11 5.593713e-01   573.7907  2.149675e-08  9.832775e-03 {565,605}
## 4                8           1802 5.703649e-09 5.000034e-01   315.2465  4.329429e-07  5.726933e-03 {570,608}
## 5               10            758 6.674710e-04 4.727684e-01   127.2270  7.274884e-05  2.353013e-03 {572,608}
## Totals          NA         115260           NA           NA 34669.2224            NA            NA

The number of (simplified) generators of zono is n = 340, indexed from 360 to 699. So the total number of parallelograms is 340(340 − 1) = 115260. Data in the first row are for the coincident parallelograms, with 2 transitions. These form the majority of ∂Z, with about 33110/34669 = 95.5% of the surface area. Data in the rows below is for the abundant parallelograms. More transitions typically have fewer parallelograms. The last column has an example of a parallelogram with the given transition count. For example, there are 1802 parallelograms in ∂Z with 8 transitions, and the one given by generators {570, 608} is one of them. This means that the line through v₅₇₀ and v₆₀₈ cuts P in 8 places. Here is a plot of the point in the cube that maps to the center of the parallelogram:

oldpar = par( omi=c(0,0,0,0), mai=c(0.45,0.5,0.1,0) )
gnd = getground( getsimplified( getmatroid(zono) ) )
pcube = boundarypgramdata( zono, c(570,608), cube=TRUE )$pcube
xlim = range( gnd[which(0<pcube)] ) + 20*c(-1,1)
plot( xlim, c(0,1), type='n', xlab='', ylab='', las=1, lab=c(5,10,7), cex.axis=0.8 )
grid( col='gray', lty=1 )
lines( gnd, pcube, type='s' )

Figure 10.2

par( oldpar )

Note that the values at 570 and 608 are both 1/2, and all the other values are 0 or 1.

The following figure is a helpful 3D visualization of all the abundant parallelograms:

library( orientlib )
user3x3 = orientlib::rotmatrix( orientlib::eulerzyx( -0.249417, 0.7116067, 2.324364 ) )@x
dim(user3x3) = c(3,3)
par3d( userMatrix=rotationMatrix(matrix=user3x3), zoom=0.35 )
plothighertrans( zono )

Figure 10.3

In this figure, the abundant parallelograms are color-coded following [3]; dark red for 4, yellow for 6, blue for 8, and purple for 10 transitions. The view is looking up the “neutral axis” with a black point at 0, a white point at the opposite point, and a gray point at the center of symmetry. The central symmetry of the abundant parallelograms is clear. Compare this with Figure 7 in [3].

References

Session Information

R version 4.4.1 (2024-06-14)
Platform: x86_64-pc-linux-gnu
Running under: Ubuntu 24.04.1 LTS

Matrix products: default
BLAS:   /usr/lib/x86_64-linux-gnu/openblas-pthread/libblas.so.3 
LAPACK: /usr/lib/x86_64-linux-gnu/openblas-pthread/libopenblasp-r0.3.26.so;  LAPACK version 3.12.0

locale:
 [1] LC_CTYPE=en_US.UTF-8       LC_NUMERIC=C              
 [3] LC_TIME=en_US.UTF-8        LC_COLLATE=C              
 [5] LC_MONETARY=en_US.UTF-8    LC_MESSAGES=en_US.UTF-8   
 [7] LC_PAPER=en_US.UTF-8       LC_NAME=C                 
 [9] LC_ADDRESS=C               LC_TELEPHONE=C            
[11] LC_MEASUREMENT=en_US.UTF-8 LC_IDENTIFICATION=C       

time zone: Etc/UTC
tzcode source: system (glibc)

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] orientlib_0.10.5 rgl_1.3.1        zonohedra_0.3-0  rmarkdown_2.28  

loaded via a namespace (and not attached):
 [1] microbenchmark_1.5.0 cli_3.6.3            knitr_1.48          
 [4] rlang_1.1.4          xfun_0.47            highr_0.11          
 [7] jsonlite_1.8.8       glue_1.7.0           buildtools_1.0.0    
[10] htmltools_0.5.8.1    maketools_1.3.0      sys_3.4.2           
[13] sass_0.4.9           evaluate_0.24.0      jquerylib_0.1.4     
[16] fastmap_1.2.0        base64enc_0.1-3      yaml_2.3.10         
[19] lifecycle_1.0.4      compiler_4.4.1       htmlwidgets_1.6.4   
[22] digest_0.6.37        R6_2.5.1             magrittr_2.0.3      
[25] bslib_0.8.0          logger_0.3.0         tools_4.4.1         
[28] cachem_1.1.0