2,133
Views
4
CrossRef citations to date
0
Altmetric
Original Articles

On Some Average Properties of Convex Mosaics

&

Abstract

In a convex mosaic in Rd we denote the average number of vertices of a cell by v¯ and the average number of cells meeting at a node by n¯. Except for the d = 2 planar case, there is no known formula prohibiting points in any range of the [n¯,v¯] plane (except for the unphysical n¯,v¯<d+1 strips). Nevertheless, in d = 3 dimensions if we plot the 28 points corresponding to convex uniform honeycombs, the 28 points corresponding to their duals and the 3 points corresponding to Poisson-Voronoi, Poisson-Delaunay and random hyperplane mosaics, then these points appear to accumulate on a narrow strip of the [n¯,v¯] plane. To explore this phenomenon we introduce the harmonic degree h¯=n¯v¯/(n¯+v¯) of a d-dimensional mosaic. We show that the observed narrow strip on the [n¯,v¯] plane corresponds to a narrow range of h¯. We prove that for every h¯(d,2d1] there exists a convex mosaic with harmonic degree h¯ and we conjecture that there exist no d-dimensional mosaic outside this range. We also show that the harmonic degree has deeper geometric interpretations. In particular, in case of Euclidean mosaics it is related to the average of the sum of vertex angles and their polars, and in case of 2 D mosaics, it is related to the average excess angle.

2010 Mathematics Subject Classification:

1. Introduction

1.1. Definition and brief history of mosaics

A d-dimensional mosaic M is a countable system of compact domains in Rd, with nonempty interiors, that cover the whole space and have pairwise no common interior points [Citation11]. We call a mosaic convex if these domains are convex and in this case all domains are convex polytopes [Citation11, Lemma 10.1.1]. In this paper we deal only with convex mosaics. We call these polytopes the cells of the mosaic, the k-dimensional faces of the cells, for k=1,2,,d1, the faces of the mosaic, and the vertices of the cells the nodes of the mosaic. In particular, in case of 3-dimensional mosaics, we may use the term face instead of facet of the mosaic. A cell having v vertices is called a cell of degree v, and a node which is the vertex of n cells is called a node of degree n. Our prime focus is to determine how average values of these quantities, denoted by n¯ and v¯, respectively, depend on each other. We remark that for planar regular mosaics, the pair {v¯,n¯} is called the Schläfli symbol of the mosaic so, by generalizing this concept, we will refer to the [n¯,v¯] plane as the symbolic plane of convex mosaics. These, and closely related global averages have been studied before and proved to be powerful tools in the geometric study of mosaics: in [Citation9] the planar isoperimetric problem restricted to convex polygons with v < 6 vertices is resolved using these quantities.

Our main focus will be face-to-face mosaics, in which any two distinct cells intersect in a common face or have empty intersection. Unless stated otherwise, any mosaic discussed in our paper will be a convex face-to-face mosaic and we will only discuss non face-to-face mosaics in Subsection 4.2. Furthermore, we assume that the mosaic is normal, that is, for some 0<r<R each cell contains a ball of radius r, and is contained in a ball of radius R (see, e.g. [Citation13]). This implies, in particular, that the volumes of the cells are bounded from above, and that the mosaic is locally finite; that is, each point of space belongs to finitely many cells. We note that a precise definition of v¯ and n¯ can be obtained in the usual way, that is, by taking the limit of the average degrees of cells/nodes contained in a large ball whose radius tends to infinity. Here, we always tacitly assume that these limits exist.

Geometric intuition suggests that v¯ and n¯ should have an inverse-type relationship: more polytopes meeting at a node implies smaller internal angles in the polytopes, which, in turn, suggests a smaller number of vertices for each polytope. To be able to verify this intuition we introduce

Definition 1.

The harmonic degree of a mosaic M is defined as (1) h¯(M)=n¯(M)v¯(M)n¯(M)+v¯(M),(1) where v¯(M),n¯(M) denote the average cell and nodal degrees of M, respectively.

The variation of the harmonic degree h¯ (computed on an ensemble of mosaics) may serve as a measure of how good our intuition was: a constant value of h¯ describes an exact inverse-type relationship while small variation of h¯ still indicates that our intuitive approach is, to some extent, justified. To describe a deeper, geometric meaning of the harmonic degree we introduce

Definition 2.

Let MRd be a mosaic, C be a cell of M and p be a vertex of C. Then the total angle Ω(C,p) of the pair (C, p) is the sum of the internal and external angles of C at p; the former defined as the surface area of the spherical convex hull of the unit tangent vectors of the edges of C at p, the latter defined as the surface area of the set of the outer unit normal vectors of C at p. The average total angle Ω¯(M) associated with the mosaic M is defined as the average of Ω(C,p), taken over all pairs (C, p) in M.

Although h¯ appears to be a combinatorial property and Ω¯ appears to be a metric property of the mosaic, nevertheless, they are closely linked, which is expressed in

Theorem 1.

Let M be a convex, face-to-face mosaic in Rd and let Sd1 denote the surface area of the d-dimensional unit sphere. Then we have h¯(M)Ω¯(M)=Sd1.

We will prove Theorem 1 in Section 3, and in Section 4 we extend it to 2-dimensional spherical mosaics. Since there is no natural definition of average for hyperbolic mosaics (cf. also Subsection 4.1.2), Theorem 1 cannot be extended to mosaics in hyperbolic planes. While Ω(M)=π is constant in d = 2 dimensions for Euclidean mosaics (implying, via Theorem 1, constant value for the harmonic degree h¯) however, if d > 2 then Ω(M) may vary, so our original intuition appears to become ambiguous for d > 2 and the variation of h¯ will serve as an indicator of this ambiguity.

In one dimension (d = 1) we have v=n=2 for each cell and vertex and thus, trivially h¯=1 for all mosaics. In two dimensions one can have cells and nodes of various degrees, nonetheless, it is known [Citation11, Theorem 10.1.6] that for all convex mosaics h¯=2.

The situation in d = 3 dimensions appears, at least at first sight, to be radically different. Schneider and Weil [Citation11] provide the general equations governing 3D random mosaics. In Section 2 we present an elementary proof that the same governing equations hold for any convex mosaic under some simple finiteness condition. These equations have three variable parameters. We also show that, beyond the trivial inequalities v¯,n¯4 these formulae do not yield additional constraints on n¯,v¯ suggesting that in the [n¯,v¯] symbolic plane, except for the unphysical domains characterized by n¯,v¯<4, we might expect to see mosaics anywhere. However, this is not the case if we look at the best known mosaics: uniform honeycombs. The latter are a special class of convex mosaics where cells are uniform polyhedra and all nodes are equivalent under the symmetry group of the mosaic. The list of all possible convex uniform honeycombs was completed only recently by Johnson [Citation8] who described 28 such mosaics (for more details on the 28 uniform honeycombs see [Citation2, Citation7] and more details on the history see [Citation10]). To provide the complete list of these 28 honeycombs has been a major result in discrete geometry. If these mosaics were spread out on the [n¯,v¯] symbolic plane, that would certainly imply that the associated values of the harmonic degree h¯ cover a very broad range. However, this is not the case: all values of h¯ are in the range 3.31h¯4. In addition, we also computed the values of h¯ associated with the 28 dual mosaics, hyperplane random mosaics, the Poisson-Voronoi and Poisson-Delaunay random mosaics and found that for the total of all the 60 mosaics the range is the same (cf. in the Appendix). The indicated narrow range for the harmonic degree implies that on the [n¯,v¯] symbolic plane the points corresponding to these mosaics appear to accumulate on a narrow strip (cf. ).

Figure 1. The 28 uniform honeycombs, their duals, the hyperplane mosaics, the Poisson-Voronoi and Poisson-Delaunay mosaics, iterated foams and their duals (for details on the latter see Section 3.2) shown as black dots on the symbolic plane [n¯,v¯] (left) and on the plane [f¯,v¯], where f¯ denotes the average number of faces of a cell of the mosaic (right). For detailed numerical data see in the Appendix. Continuous curve on the left panel shows prismatic mosaics. Dotted lines represent the h¯=3 and h¯=4 curves, illustrating Conjecture 1. Continuous straight lines on the right panel correspond to simple and simplicial polyhedra.

Figure 1. The 28 uniform honeycombs, their duals, the hyperplane mosaics, the Poisson-Voronoi and Poisson-Delaunay mosaics, iterated foams and their duals (for details on the latter see Section 3.2) shown as black dots on the symbolic plane [n¯,v¯] (left) and on the plane [f¯,v¯], where f¯ denotes the average number of faces of a cell of the mosaic (right). For detailed numerical data see Table A1 in the Appendix. Continuous curve on the left panel shows prismatic mosaics. Dotted lines represent the h¯=3 and h¯=4 curves, illustrating Conjecture 1. Continuous straight lines on the right panel correspond to simple and simplicial polyhedra.

While we can not offer a full explanation of this phenomenon, we think that the concept of the harmonic degree may help to explain its essence. In particular, we introduce

Conjecture 1.

For any normal, face-to-face mosaic M in Rd, we have h¯(M)(d,2d1].

To build intuitive support for Conjecture 1 we will show in Section 3 that the interval indicated in the Conjecture has indeed some significance: we demonstrate mosaics corresponding to the lower and upper endpoints (the former understood as a limit outside the interval) and we also prove

Theorem 2.

For all h¯(d,2d1], there is a normal, face-to-face mosaic M in Rd satisfying h¯(M)=h¯.

Also, as a small step towards establishing the Conjecture, we prove

Proposition 1.

For any normal, face-to-face mosaic M in Rd, we have h¯(M)d+12. Furthermore, if d = 3, then h¯(M)2813.

We provide the general formulae governing 3 D mosaics in Section 2. Next, we prove Theorems 1 and 2 in Section 3. Section 4 discusses non-Euclidean mosaics and non-face-to-face mosaics in d = 2 and d = 3 dimensions. In Section 5 we draw conclusions.

2. General formulae defining 3D mosaics

In [Citation11], for any 0i,jd and for any random mosaic M in the d-dimensional Euclidean space Rd, the quantity nij is defined as the number of j-faces of a typical i-face of M if ji, and as the number of j-faces containing a typical i-face of M if j > i. Relations between these quantities are described in [Citation11, Theorem 10.1.6] for the case d = 2, and in [Citation11, Theorem 10.1.7] for the case d = 3. Here we use elementary, combinatorial arguments to show that these relations hold for any convex mosaic in R3.

Throughout this section, let M be a convex, face-to-face, normal mosaic in Rd. Then we may define nij(M) as the average number of j-faces contained in or containing a given i-face, if ji or j > i, respectively. If it is clear which convex mosaic M we refer to, for brevity we may use the notation nij=nij(M). Here we assume that the average of any nij, for all values of i and j exists.

Theorem 3.

For any convex mosaic M in R3 satisfying the conditions in the previous paragraph, we have (2) [nij(M)]=[1(f2)nv+2(f2)nv+nn212(v+f2)n(f2)n+2v2(v+f2)n(f2)n+2v2(v2)f+22(v2)f+212vv+f2f1],(2) where v=n30,f=n32 and n=n03.

Proof.

Clearly, nii = 1 for i=1,2,3,4, and since each face belongs to exactly two cells, and each edge has exactly two endpoints, we have n23=n10=2. The formula n31=v+f2 follows from applying Euler’s formula for each cell of M, and observing that then the same formula holds for the average numbers of faces, edges and vertices of a cell.

Let r be sufficiently large, and let Br be the Euclidean ball, centered at the origin o and with radius o. Let Nv(r),Ne(r),Nf(r) and Nc(r) denote the number of vertices, edges, faces and cells of M in Br, respectively.

Note that if r is sufficiently large, the sum of the numbers of edges of all faces in Br is approximately Nf(r)n21, and since almost all face in Br belongs to exactly two cells in Br, and each edge of a given cell belongs to exactly two faces of the cell, we have that this quantity is approximately equal to Nc(r)n31. On the other hand, the sum of the numbers of faces the cells in Br have is approximately Nc(r)f2Nf(r). More specifically, we have f2=limrNf(r)Nc(r)=n31n21, which readily yields that n21=n20=2(v+f2)f.

Note that the number of cell-vertex incidences in Br is approximately Nv(r)nNc(r)v. Furthermore, for any incident cell-vertex pair C, v, the number of faces that contain the vertex and is contained in the cell is equal to the number of edges with the same property. Let us denote this common number by degC(v), which then denotes the degree of the vertex v in the cell C. We compute the approximate value of the quantity Q=CBr,vCdegC(v) in two different ways.

On one hand, we have Q=CBr2e(C)2n31Nc(r), where e(C) denotes the number of the edges of the cell C. On the other hand, since any face belongs to exactly two cells, we also have Q=vBrCBr,CvdegC(v)2n02Nv(r).

More precisely, we have obtained that nv=limrNc(R)Nv(r)=n02n31, which implies the expression for n02.

The value of n01 can be obtained from the application of Euler’s formula for the vertex figure at every node. Finally, the value of n12=n13 can be obtained from the values of the other nijs like the value of n20=n21.

Remark 1.

By Theorem 3, it seems that many combinatorial properties of the convex mosaic M are determined by three parameters, say by v, f, n. One may try to find upper and lower bounds for these values by observing that each entry in [nij] has a minimal value: e.g. n30,n32,n03,n014 and n12,n213. Nevertheless, solving these inequalities puts no restriction on the values of v, f, n, apart from the trivial inequalities n,v,f4. It is worth noting that in contrast, for convex polyhedra (or, in other words, for convex spherical 2-dimensional mosaics, cf. Remark 8), the sharp inequalities v2+2f2v+4 [Citation14, Citation15] are immediate consequences of the fact that each face of the polyhedron has at least 3 vertices, and each vertex belongs to at least 3 faces.

Remark 2.

Note that if M is a convex mosaic in R3 and a convex mosaic M° is its dual, then nij(M°)=n(3i)(3j)(M), for all 0i,j3.

3. Proof of the theorems

3.1. Proof of Theorem 1 and the volumes of polar domains

Proof.

First we show that in case of Euclidean mosaics (in arbitrary dimensions) the harmonic degree may be interpreted as the averaged inverse sum of two angles linked by polarity, one of which is the internal vertex angle of a cell.

Consider a convex face-to-face mosaic M in Rd. For any cell C in M and any vertex p of C, let I(C,p)Sd1 denote the set of unit vectors such that the rays in the direction of a vector in I(C, p) and starting at p contain points of C{p}. Furthermore, let E(C,p)Sd1 denote the set of outer unit normal vectors of C at p. Then, by definition, we have that E(C, p) is the polar (I(C,p))° of I(C, p). Let us denote the spherical volumes of E(C, p) and I(C, p) by ΩE(C,p) and ΩI(C,p), respectively, and let Ω¯E,Ω¯I define the average values of ΩE(C,p) and ΩI(C,p), respectively, over all incident pairs C and p.

Note that for any cell C, the family of sets E(C, p), where p runs over the vertices of C, is clearly a spherical mosaic of Sd1, and thus, the total area of the members of this family is the surface area Sd1 of the sphere. The same statement holds for the family of sets I(C, p), where C runs over the cells containing a given node p.

Now, consider a large ball B of space with radius r, and denote by Nc and Nv the numbers of cells and nodes of M in B, respectively. Then, for the number k(r) of incident pairs of cells and vertices in B we have (3) k(r)Ncv¯Nvn¯.(3)

The sums ωI,ωE of ΩI(C,p) and ΩE(C,p) (over all pairs of cells C and incident vertices p in B) may be written as: (4) ωINvSd1ωENcSd1,(4) so, for the averages Ω¯I=limr(ωI/k),Ω¯E=limr(ωE/k) we get (5) Ω¯In¯=Ω¯Ev¯=Sd1.(5)

Thus, by (Equation5) we have (6) Ω¯=Ω¯I+Ω¯E=Sd1v¯+Sd1n¯,(6) implying that (7) h¯Ω¯=Sd1.(7)

Remark 3.

Substituting the value of Sd1 into (Equation7), we obtain that for planar mosaics h¯=2πΩ¯, and for mosaics in R3h¯=4πΩ¯.

Remark 4.

If d = 2, then at each vertex we have ΩI(C,p)+ΩE(C,p)=π, implying Ω¯=π and this, via equation (Equation7) yields h¯=2.

Remark 5.

As we observed, for any node p and any cell C incident to p, we have {p:pC}ΩE(C,p)={C:pC}ΩI(C,p)=Sd1.

While the equality {C:pC}ΩE(C,p)=Sd1 does not hold in general, it does hold in case of hyperplane mosaics.

Remark 6.

Clearly, the inequalities v¯,n¯4 readily imply h¯2, and by Theorem 1, Ω¯12Sd1. This inequality is also an immediate consequence of the well-known result of Gao, Hug and Schneider [Citation6], stating that for any spherically convex set A of a given spherical volume, the volume of its polar A° is maximal if A is a spherical cap of the given spherical volume.

3.2. Proof of Theorem 2 and the range of the harmonic degree

3.2.1. Mosaics with high harmonic degree: hyperplane mosaics

If M is generated by dissecting Rd with (d1)-dimensional hyperplanes then it is called a hyperplane mosaic [Citation11]. An elementary computation shows that the harmonic degree of a normal mosaic, generated by hyperplanes in general position, is (8) h¯=2(d1).(8)

These mosaics appear to have the highest harmonic degree. They are certainly not the only mosaics with h¯=2d1, though. In d = 2 dimensions all convex mosaics have h¯=2 and in d = 3 dimensions we have the continuum of prismatic mosaics with h¯=4.

3.2.2. Mosaics with low harmonic degree: iterated foams and their duals

Here we define mosaics which appear to have extremely low harmonic degrees.

Consider a Euclidean mosaic M=M0 with n¯0=d+1 as the average degree of nodes; we remark that such mosaics exist in all dimensions, we construct the dual of such a mosaic in the proof of Theorem 2. In addition, we assume that the edge lengths of the mosaic are uniformly bounded; that is there are some 0<a<b such that the value of each such quantity is between a and b, and we assume the same about the angles between any two faces of M.

Note that since all d-dimensional convex polytopes with d + 1 vertices are simplices, the vertex figures of ‘almost all’ nodes of M are simplices. Now, for each node having a simplex as a vertex figure, replace the node with its vertex figure. More precisely, if p is a node whose vertex figure is a simplex, define the cell Cp as the convex hull of the points of the edges starting at p, at the distance ε>0 from p for some fixed value of ε independent of p, and replace each cell C containing p with the closure of CCp. Then, if this process is carried out simultaneously at all nodes p, we obtain a convex, face-to-face mosaic M1, which, under our condition, is normal. Applying this procedure k times we obtain the convex, face-to-face, normal mosaic Mk. We will call the k limit of such a sequence a d-dimensional iterated foam, referring to the fact that in a physical foam in d = 2 and d = 3 dimensions we always have n¯=d+1.

Clearly, for all k1, we have n¯k=n¯(Mk)=d+1. Consider a sufficiently large region of space. Then the number of vertex-cell incident pairs in M is approximately Ncv¯Nvn¯=Nv(d+1), where Nc and Nv denote the numbers of the cells and the nodes of the mosaic in this region, respectively. An elementary computation yields that for the mosaic M1, this number is approximately Ncdv¯+(d+1)Nv(d+1)Ncv¯, and the number of cells of M1 in this region is about Nc+Nv(1+vd+1)Nc. Thus, taking limit, we obtain that the average degree of a cell of M1 is v¯(M1)=(d+1)2v¯d+1+v¯. Setting v¯k=v¯(Mk), we similarly obtain the recursive formula v¯k+1=(d+1)2v¯kd+1+v¯k for all nonnegative integers k.

An elementary computation yields that |v¯k+1d(d+1)|=(d+1)|v¯kd(d+1)|d+1+v¯k12|v¯kd(d+1)| for all v¯kd+1. This implies that for any initial value v¯d+1, the sequence {v¯k} converges to d(d+1), and thus, the sequence {h(Mk)} converges to d(d+1)2d(d+1)+(d+1)=d.

We note that the above procedure can be dualized. In this case, starting with a mosaic in which all cells are simplices, in each step we divide the cell into regions by taking the convex hulls of a given interior point of the cell with each facet of the cell. Lines 31 and 31 of in the Appendix summarize the main parameters of these iterated mosaics.

Remark 7.

We note that for planar mosaics the iterating process (and also its dual), can be extended to any mosaic in a natural way, and after one iteration step the degree of every node (in case of its dual the degree of every cell) is equal to 3. This is illustrated in where we iterate a (finite domain of a) hyperplane mosaic for k = 2 steps in both directions.

Figure 2. Illustration of an iterated foam and its dual in d = 2 dimensions. We used the hyperplane mosaic (middle panel) as initial condition and ran k = 2 iterative steps both in the direction of iterated foams (upper panel) as well as their duals (lower panel). Note that in d = 2 dimensions these iterative steps change both n¯ and v¯, however, the harmonic degree remains constant at h¯=2. Also note that in higher dimensions hyperplane mosaics may not be used as initial conditions for these iterations. Iterated foams and their duals in d = 3 dimensions are shown in the symbolic plane on .

Figure 2. Illustration of an iterated foam and its dual in d = 2 dimensions. We used the hyperplane mosaic (middle panel) as initial condition and ran k = 2 iterative steps both in the direction of iterated foams (upper panel) as well as their duals (lower panel). Note that in d = 2 dimensions these iterative steps change both n¯ and v¯, however, the harmonic degree remains constant at h¯=2. Also note that in higher dimensions hyperplane mosaics may not be used as initial conditions for these iterations. Iterated foams and their duals in d = 3 dimensions are shown in the symbolic plane on Figure 1.

3.2.3. Proof of Theorem 2

Let M be the standard cubic mosaic in Rd, whose vertices are the points of the integer lattice Zd, and note that h¯=2d1. We define a new lattice M as the first barycentric subdivision of M. In this lattice the centroid of each face of M is a vertex of M, and cells correspond to flags of M, where a flag is a sequence F0F1F2Fd of faces of M, with dimFi=i for all values of i. In this case the cell associated to the flag is the convex hull of the centroids of the Fis.

We compute the harmonic degree of M. Note that since every cell of M is a simplex, we have v¯(M)=d+1. First, observe that since any cell of M has 2d facets and by the fact the every face of a cube is a cube, choosing the faces of a flag in the order Fd,Fd1,,F0, we have that the number of flags belonging to any given cube in the mosaic is 2d·(2d2)··2=2dd!. We note that the same quantity can be obtained if we choose the faces of a flag in the opposite order. In this approach first we choose a vertex of the cell, then we extend this point to an edge parallel to a chosen coordinate axis, which then can be extended to a 2-face choosing another coordinate axis. In this way the number of flags is equal to the product of the number of vertices (2d), and the number of permutations of the d coordinate axes (d!).

Applying arguments similar to these two counting arguments, one may show that each i-face belongs to 2ii!(di)! flags within one cell, and as each i-face belongs to 2di cells, the total number of flags an i-face belongs to is 2di!(di)!. Furthermore, the proportion of the i-faces compared to the number of cells is (di). Thus, the average degree of a node in the barycentric subdivision of the cubic lattice is n¯(M)=i=0d2di!(di)!(di)i=0d(di)=(d+1)!, implying (9) h¯=h¯(M)=(d+1)!1+d!,(9) where an elementary computation yields that d(d+1)!1+d!<d+1 for all d1.

Case 1, h¯=(d+1)!1+d!h¯h¯=2d1. We construct a mosaic with harmonic degree h¯. To do it, we use four types of layers.

A first type layer is a translate of the part of the cubic lattice between the hyperplanes {xd=0} and {xd=1}. A second type layer is the same part of the subdivided cubic lattice M. For the third type, we take the translates of a partial subdivision of the cubic lattice: each cube in the strip between {xd=0} and {xd=1} is subdivided by the centroids of all faces apart from those in the hyperplane {xd=1}. The fourth type layers are the reflected copies of third type layers about the hyperplane {xd=0}.

The building bricks of the mosaic are strips S(k, l) of width k+l+2, where k and l are positive integers. Here S(k, l) consisting of k first type, 1 fourth type, l second type and 1 third type layer in this consecutive order, where the layers are attached in a face-to-face way. Observe that if k and l are sufficiently large, then the harmonic degree of a strip S(k, l) is approximately kk+lh¯+lk+lh¯.

Since h¯h¯h¯, there is some 0λ1 such that h¯=λh¯+(1λ)h¯. Let {(km,lm)} be a sequence of pairs of positive integers such that km+lm, and kmkm+lmλ.

We define the mosaic M as follows. Consider a strip S1=S(k1,l1). Attach two copies of S(k2,l2) to the two bounding hyperplanes of S1 in a face-to-face way, to obtain S2 as the union of these three strips. Then S3 is constructed by attaching two copies of S(k3,l3) to S2 in a face-to-face way. Continuing this procedure, we obtain the mosaic M as the limit of the strip Sm, where m. Then the harmonic index of M is h¯.

Case 2, d<h¯<h¯. Observe that in the subdivided cubic mosaic M defined above, every cell is a simplex. Thus, we may apply the dual of the algorithm discussed in Subsection 3.2.2, namely in each step we divide each cell C into d + 1 new cells by taking the convex hulls of a given interior point of C and the facets of C. Let us denote by Mk and h¯k the mosaic obtained by k subsequent applications of this procedure, and its harmonic degree, respectively. Then the sequence {h¯k} tends to d, and thus, there is a smallest value of k such that h¯ is in the interval [h¯k+1,h¯k]. To construct a suitable mosaic M with harmonic degree h¯, we follow the idea of the proof in Case 1, and divide only a part of the cells of Mk into new cells.

3.2.4. Proof of Proposition 1

The first part of the proposition follows from the trivial estimates v¯,n¯d+1. To prove the second part, we need a lemma. We note that the minimum number of tetrahedra such that each convex polyhedron with k vertices can be decomposed into is not known. This fact and the idea of the proof of Lemma 1 can be found in [Citation4].

Lemma 1.

Any convex polyhedron P in R3 with v vertices can be decomposed into at most 2v7 tetrahedra.

Proof.

Let the faces of P be G1,,Gf, and let fi denote the number of edges of Gi. Then i=1ffi=2e=2v+2f4, where e is the number of edges of P.

Let p be any vertex of P. Let us triangulate each face of P containing p by the diagonals starting at p, and all other faces of P by the diagonals starting at an arbitrary vertex of the face. Then the number of all triangles is i=1f(fi2)=2v+2f42f=2v4. Since each face contains at least one triangle, and each vertex belongs to at least three faces, the number m of triangles in the faces not containing p is at most m2v7. Now, if these triangles are T1,T2,,Tm, then the tetrahedra conv({p}Ti),i=1,2,,m is a required decomposition of P.□

Consider a mosaic M in R3, and a sufficiently large region. Let Nc and Nv denote the numbers of cells and nodes of M in this region. For any cell Ci, let vi denote the number of vertices of Ci. Then the number of cell-vertex incidences in this regions is approximately iviNcv¯Nvn¯.

By Lemma 1, these cells can be decomposed into at most i(2vi7)2Ncv¯7Nc tetrahedra. It is well known that the sum of the internal angles of any tetrahedron is greater than 0 and less than 2π [Citation5]. Thus, the sum of all the internal angles of the cells is at most 4πNcv¯14πNc. On the other hand, this sum is approximately equal to the product of the number of nodes and the total angle of a sphere; that is 4πNv. Thus, apart from a negligible error term, we have 4πNcv¯n¯4πNcv¯14πNc. Taking a limit, we obtain that 2v¯n¯2v¯7, implying that n¯2v¯2v¯7. Since n¯4 clearly holds, we have that (10) n¯max{4,2v¯2v¯7}.(10)

It is an elementary computation to check that 42v¯2v¯7 if and only if v¯143. Since for any fixed value of n¯,h¯ is minimal at the minimal value of v¯ it follows that under the condition that v¯143, we have h¯2813. Furthermore, if 4v¯143, then h¯=2v¯2v¯5, which is minimal if v¯=143, and thus, h¯2813 also in this case.

4. Non-Euclidean and non face-to-face mosaics

4.1. Non-Euclidean mosaics

Mosaics, convex mosaics, and all notions described in Subsection 1.1, excluding the notions of average degrees of cells and vertices, can be defined in a natural way for spherical and hyperbolic spaces as well. For spherical space, this includes average degrees as well; because of the compactness of the space it is even possible to avoid the usual limit argument applied to compute these values in Rd.

On the other hand, defining average values in hyperbolic space seems problematic. Indeed, it is well known that under rather loose restrictions, in a packing of congruent balls in Hd, the number of balls intersecting the boundary of a hyperbolic ball B of large radius is not negligible compared to the number of balls contained in B. This phenomenon is explored in more details, for instance, in [Citation3], and can be generalized for the numbers of cells of a normal mosaic in a natural way.

A straightforward solution to this problem is to examine only regular mosaics, in which the degree of every cell, and the degree of every vertex is equal, which offers a natural definition for n¯ and v¯. We do this in Subsection 4.1.1. To circumvent this problem in a more general way, we use the geometric interpretation of harmonic degree for mosaics in Rd, appearing in Subsection 3.1; this interpretation, in particular, provided a different proof of the fact that harmonic degree is 2 for every planar Euclidean mosaic.

In Subsection 4.1.2 we generalize this geometric interpretation for mosaics in S2 and H2, and show that for spherical mosaics it coincides with the original definition of harmonic degree. Finally, we show that this value is less than 2 for any spherical mosaic, and it is at least 2 for any hyperbolic mosaic, using any reasonable interpretation of average.

4.1.1. Non-Euclidean regular honeycombs in Sd,Hd for d = 2, 3

Here we show that in d = 2 dimensions, Euclidean mosaics separate regular spherical mosaics from regular hyperbolic mosaics on the [n¯,v¯] symbolic plane.

While Plato’s original idea of filling the Euclidean space with regular solids proved to be incorrect, if we relax the condition that the embedding space has no curvature then all Platonic solids may fill space by what we call a regular honeycomb. We briefly review these mosaics to show how they are represented in our notation and how their harmonic degrees are spread.

Let M be a honeycomb in a space of constant curvature of dimension d. A sequence F0F1Fd, where Fi is an i-dimensional face of M, is called a flag of M (cf. the proof of Theorem 2). We say that M is regular, if for any two flags of M there is an element of the symmetry group of M that maps one of them into the other one. In particular, if M is a regular planar mosaic, then the cells of M are congruent regular p-gons, and at each node, an equal q number of edges meet at equal angles. In this case {p,q} is called the Schläfli symbol of M. It is well known that up to congruence, for any values p,q3, there is a unique regular mosaic with Schläfli symbol {p, q} (cf. [Citation12]). This mosaic if spherical if p = 3 and q = 3, 4, 5 or if q = 3 and p = 3, 4, 5, Euclidean if {p,q}={3,6},{4,4},{6,3}, and hyperbolic otherwise. We note that the five regular spherical honeycombs correspond to the five Platonic polyhedra. The Schläfli symbol of a higher dimensional mosaic can be defined recursively: it is {p1,p2,,pd} if the Schläfli symbol of its cells are {p1,p2,,pd1} (which must correspond to a regular spherical mosaic), and the intersection of M with any sufficiently small sphere centered at a node of M is the regular spherical mosaic {p2,p3,,pd}.

In d = 2 dimensions the h¯=2 curve defines a partition of the Z2 grid on the [n¯,v¯] symbolic plane with the constraints n¯,v¯3. For a regular mosaic with Schläfli symbol {p,q}, set v¯=p,n¯=q, or equivalently, h¯=pqp+q. Then an elementary computation (determining the sign of the quantity 1p+1q12 for all integers p,q3) shows that grid points on the h¯=2 line correspond to regular Euclidean mosaics, grid points with h¯<2 correspond to regular spherical mosaics and grid points with h¯>2 correspond to regular hyperbolic mosaics.

In d = 3 dimensions the h¯=4 curve defines a partition of the Z2 grid on the [n¯,v¯] symbolic plane in a similar sense, although here only a finite number of grid points correspond to regular mosaics. We summarize these in .

Table 1. Regular honeycombs in d = 3 dimensions.

As we can observe, the harmonic degree h¯ of a mosaic appears to carry information both on the dimension and the curvature of the embedding space: h¯=constant curves separate convex mosaics embedded in spaces with the same curvature sign but different dimension and vice versa, they also separate regular mosaics embedded in spaces with the same dimension but different sign of curvature. Knowing one of those parameters seems to permit us to obtain the other, based on the mosaic’s harmonic degree.

4.1.2. Non-Euclidean general face-to-face mosaics on S2 and H2

Our goal is to extend the geometric interpretation of the harmonic degree to convex face-to-face mosaics on S2 and H2. First we describe how the duals of spherical mosaics can be constructed. To do this, first we compute the harmonic degree of spherical mosaics directly.

Remark 8.

Clearly, projecting a convex polyhedron P from an interior point to a sphere concentric to this point yields a spherical mosaic. Furthermore, in a spherical mosaic any two cells intersect in one edge, one vertex or they are disjoint. Using these properties it is easy to show that the edge graph of any spherical mosaic is 3-connected and planar; such an argument can be found, e.g. in the proof of [Citation1, Claim 9.4]. By a famous theorem of Steinitz [Citation15], every 3-connected planar graph is the edge graph of a convex polyhedron. Thus, up to combinatorial equivalence, we may regard a spherical mosaic as the central projection on S2 of a convex polyhedron P containing the origin in its interior. This representation permits us to define the dual of a spherical mosaic associated to P as the mosaic associated to its polar convex polyhedron P°.

In two dimensions, spherical mosaics may be characterized by the angle excess associated with their cells which is equal to the solid angle subtended by the cell or, alternatively, the spherical area of the cell. Let M be a convex mosaic on S2 with Nv nodes and Nc cells. Since M is a tiling of S2, the average area of a cell is ΩC=4πNc. Similarly, the average area of a cell in the dual mosaic is ΩN=4πNv.

Definition 3.

For any spherical mosaic M, we call the quantity μ¯(M)=1πΩCΩNΩC+ΩN the harmonic angle excess of M.

Proposition 2.

The harmonic degree of any convex, face-to-face mosaic M on S2 is (11) h¯(M)=2μ¯(M).(11)

Proof

. Let Nc and Nv denote the numbers of cells and nodes of M, and let v¯ and n¯ denote the average degree of a cell and a node, respectively. Then the number of adjacent pairs of cells and nodes of M is equal to (12) v¯Nc=n¯Nv.(12)

Let αij denote the angle of the cell Ci at the vertex vj if they are adjacent, and let αij=0 otherwise. We compute the sum i,jαij in two different ways. First, note that i,jαij=jiαij=2πNv. On the other hand, the area of any cell Ci is equal to the angle sufficit of Ci, or more specifically, area(Ci)=jαij(deg(Ci)2)π, where deg(Ci) is the number of vertices of Ci (see Subsection 1.1). Since iarea(Ci)=area(S2)=4π and ideg(Ci)=v¯C, it follows that i,jαij=4π+v¯Ncπ2Ncπ. This implies the equality (13) 2Nv=v¯Nc2Nc+4.(13)

Now, (Equation11) follows from (Citation12, Citation13) and the equation μ¯=4Nv+Nc (which follows from Definition 3).□

Corollary 1.

The harmonic degree of any face-to-face convex mosaic M of S2 is h¯(M)<2.

While it does not seem feasible to extend the definition of h¯ for mosaics in H2 in a straightforward way, the geometric interpretation of this quantity in Subsection 4 permits us to find a variant of Corollary 1 also in this case.

Let M be a convex face-to-face mosaic in any of the planes R2,S2 or H2. Let C be a cell of M with v vertices. Let pj, j=1,2,,v be the vertices of C, and fix an arbitrary point q int C. Let Lj denote the sideline of C passing through the vertices pj and pj+1, and let Rj denote the ray starting at q and intersecting Lj in a right angle. The convexity of C implies that the rays R1,R2,,Rv are in this cyclic order around q. Let ΩE(C,pj) denote the angle of the angular region which is bounded by Rj1Rj and whose interior is disjoint from all the rays Rj. Furthermore, let ΩI(C,pj) denote the interior angle of C at pj. Now we define the quantity Ω¯(C)=j=1v(ΩE(C,pj)+ΩI(C,pj))v=2π+Λ(C)v, where Λ(C) is the sum of the interior angles of C.

Observe that if M is a Euclidean mosaic, then the weighted average value of Ω¯(C), with the weight equal to v, over the family of all cells of M coincides with Ω¯.

Next, assume that M is a spherical mosaic. Let the cells of M be Ci, i=1,2,,Nc, and let Nv and Ne be the number of nodes and edges of the mosaic, respectively. If the degree of Ci is vi, then i=1Ncvi=2Ne, and by Euler’s formula, Nv+Nc=Ne+2, yielding μ¯=4Nc+Nv=4Ne+2. Furthermore, for all values of i, the area formula for spherical polygons yields that Λ(Ci)=(vi2)π+area(Ci). Thus, Ω¯(Ci)=viπ+area(Ci)vi. Since the total area of all cells is 4π, this implies Ω¯=i=1NcΩ¯(Ci)vii=1Ncvi=πi=1Ncvi+i=1Ncarea(Ci)2Ne=Neπ+2πNe=2π2μ¯.

We have shown that for face-to-face, convex mosaics on S2, we have h¯=2μ¯, (cf. (Equation11)). Thus, for these mosaics we have h¯=2πΩ¯, extending Theorem 1 for 2-dimensional spherical mosaics.

Finally, consider the case that M is a hyperbolic mosaic. Let Ci,i=1,2, denote the cells of M, and let vi denote the degree of Ci. As in the spherical case, by the area formula for hyperbolic polygons, we have that Ω¯(Ci)=πarea(Ci)vi<π for all values of i. For any nonnegative function f:NR, we may define the harmonic degree of M with respect to f as h¯f=limk2πi=1kf(i)vii=1kf(i)viΩ¯(Ci), where the inequalities Ω¯(Ci)<π,iN imply h¯f2. Note that since any measure on a countable set is atomic, the above formula exhausts all reasonable possibilities for defining harmonic degree.

4.2. Non face-to-face mosaics on R2 and S2

Conjecture 1 formulates the hypothesis that the harmonic degree of d-dimensional Euclidean face-to-face mosaics is confined to the range (d,2d1]. In the current subsection we would like to point out that in case of non face-to-face mosaics this range may be much broader. According to the convention introduced in Subsection 1.1, the degree of a node is equal to the number of vertices coinciding at that node, both for face-to-face and non face-to-face convex mosaics.

In d = 2 dimensions we already stated that for face-to-face mosaics we have h¯=2 [Citation11, Theorem 10.1.6], which is equivalent to (14) n¯=2v¯v¯2.(14)

If we admit non face-to-face mosaics and we sum the internal angles over all cells and also sum the same angles as nodal angles over all nodes then (Equation14) generalizes to (15) n¯=2v¯v¯p1,(15) where p is the proportion of the regular nodes in the family of all nodes, where we call a node regular if it is the vertex of every cell it belongs to. As we can see, in 2 dimensions convex mosaics have two free parameters and they form a compact, 2D subset of the [n¯,v¯] symbolic plane as illustrated in . By computing the harmonic degree h¯ over the admissible domain marked on we find that 1.33h¯2 which indicates that non face-to-face mosaics may admit lower harmonic degrees than face-to-face mosaics. (b) shows an example of a non face-to-face mosaic in d = 3 constructed as alternated, shifted layers of a brick-wall-type planar mosaic. At every node just 2 vertices meet so we have n¯=2 and each cell is a cuboid yielding v¯=8. This results in a value h¯=1.6 which is certainly below the maximal value of h¯=2 for planar mosaics.

Figure 3. (a) Symbolic plane for planar mosaics. The p = 1 line corresponds to face-to-face mosaics. Gray shaded area marks the descriptors of all admissible mosaics in the plane. (b) Example of a special 3D mosaic with h¯<2. Solid line: odd layer, dotted line, even layer. Both layers correspond to the planar mosaic in panel (a) at (n¯,v¯)=(2,4). (c) Parameter plane for spherical mosaics in d = 2 dimensions. All mosaics shown with Nc+Nv200, Nc denoting the number of cells, Nv denoting the number of nodes. Mosaics on the v¯=3 and n¯=3 lines correspond to simple and simplicial polyhedra, respectively. Observe how mosaics accumulate on the line corresponding to face-to-face Euclidean mosaics.

Figure 3. (a) Symbolic plane for planar mosaics. The p = 1 line corresponds to face-to-face mosaics. Gray shaded area marks the descriptors of all admissible mosaics in the plane. (b) Example of a special 3D mosaic with h¯<2. Solid line: odd layer, dotted line, even layer. Both layers correspond to the planar mosaic in panel (a) at (n¯,v¯)=(2,4). (c) Parameter plane for spherical mosaics in d = 2 dimensions. All mosaics shown with Nc+Nv≤200, Nc denoting the number of cells, Nv denoting the number of nodes. Mosaics on the v¯=3 and n¯=3 lines correspond to simple and simplicial polyhedra, respectively. Observe how mosaics accumulate on the line corresponding to face-to-face Euclidean mosaics.

Remark 9.

Using the proof of Proposition 2, the generalization of formula (Equation15) to 2D spherical mosaics is straightforward: (16) v¯=(2μ¯)n¯n¯+μ¯1p.(16)

5. Summary

In this paper we proposed to represent mosaics in the [n¯,v¯] symbolic plane of average nodal and cell degrees and we introduced the harmonic degree h¯, constant values of which appear as curves in this space. We pointed out that these curves appear to have special significance: in d = 2 dimensions all convex, face-to-face mosaics appear as points of the h = 2 curve and a compact domain can be associated to non face-to-face mosaics. We showed that in case of 2D spherical mosaics h¯ differs only in a constant from the suitably averaged angle excess and this explains why points associated with 2D regular mosaics on manifolds with constant curvature are separated by the h¯=2 line.

The most interesting geometric interpretation of h¯ appears to be Theorem 1, stating that the harmonic degree is the inverse of the averaged sum of two angles associated with polar domains, one of which is the internal angle of a cell at a vertex of the cell. We showed that this interpretation of h¯ remains valid for Euclidean mosaics in arbitrary dimensions as well as 2D spherical mosaics. The link established in Theorem 1 between the harmonic degree h¯ and the average total angle Ω¯ illustrates that the combinatorial and metric properties of convex mosaics are closely related. While Ω is constant in 2D (resulting in Ω¯=π,h¯=2), in 3 D there exists a broad range in which Ω may fluctuate. Nevertheless, we found that for a set of 60 mosaics (which included all uniform honeycombs as well as random mosaics) the actual fluctuation is very small and the harmonic degree of all investigated mosaics was in the range 3.3h¯4. By using a recursive algorithm we also constructed d-dimensional Euclidean mosaics which approach, as the number of recursive steps tends to infinity, the harmonic degree h¯=d. We proved that h¯ may assume any value in the interval (d,2d1].

All the above computations and results led us to formulate Conjecture 1, stating that there exist no Euclidean, normal, face-to-face mosaics the harmonic degree of which lies outside the (d,2d1] interval. If true, this conjecture would not only yield an interesting alternative explanation for the averaged behavior of 1D and 2D mosaics but also deepen our current understanding of 3D (and higher dimensional) honeycombs.

Acknowledgments

The authors are very grateful to Rolf Schneider for his repeated encouragement which contributed to shape this manuscript. We also thank Egon Schulte and Frank Morgan for their positive comments, and an anonymous referee for careful reading and valuable comments.

Declaration of Interest

No potential conflict of interest was reported by the authors.

Additional information

Funding

Supported by the NKFIH Hungarian Research Fund grant 119245 and of grant BME FIKP-VÍZ by EMMI is kindly acknowledged. ZL has been supported by grant UNKP-19-4 New National Excellence Program of the Ministry of Innovation and Technology and the János Bolyai Research Scholarship of the Hungarian Academy of Sciences.

References

  • Bezdek, K., Lángi, Z., Naszódi, M, Papez, P. (2007). Ball-polyhedra. Discrete Comput. Geom. 38: 201–230. doi:10.1007/s00454-007-1334-7
  • Deza, M, Shtogrin, M. (2000). Uniform partitions of 3-space, their relatives and embedding. Eur. J. Combin. 21: 807–814. doi:10.1006/eujc.1999.0385
  • Fejes Tóth, G, Kuperberg, W. (1993). Packing and covering with convex sets, Chapter 3.3 Handbook of Convex Geometry. Amsterdam: North-Holland, pp. 799–860.
  • Fung, S. P. Y., Wang, C, Chin, F. Y. L. (2007). Approximation algorithms for some optimal 2D and 3D triangulations In: T. F. Gonzalez, ed. Handbook of Approximation Algorithms and Metaheuristics. Boca Raton, FL: Chapman& Hall/CRC.
  • Gaddum, J. W. (1952). The sums of the dihedral and trihedral angles in a tetrahedron. Amer. Math. Monthly. 59: 370–371. doi:10.2307/2306805
  • Gao, F., Hug, D, Schneider, R. (2003). Intrinsic volumes and polar sets in spherical space. Math. Notes. 41: 159–176.
  • Grünbaum, B. (1994). Uniform tilings of 3-space. Geombinatorics. 4: 49–56.
  • Johnson, N. W. (1991). Uniform polytopes. manuscript.
  • Chung, P. N., Fernandez, M. A., Li, Y., Mara, M., Morgan, F., Plata, I. R., Shah, N., Vieira, L. S, Wikner, E. (2012). Isoperimetric pentagonal tilings. Notices Amer. Math. Soc. 59: 632–640. doi:10.1090/noti838
  • Senechal, M. (1981). Which tetrahedra fill space? Math. Mag. 54(5): 227–243. doi:10.2307/2689983
  • Schneider, R, Weil, W. (2008). Stochastic and Integral Geometry. Berlin, Germany: Springer-Verlag.
  • Schulte, E. (1997). Symmetry of polytopes and polyhedral. In Handbook of Discrete and Computational Geometry. Boca Raton, FL: CRC Press Ser. Discrete Math. Appl., CRC, pp. 311–330.
  • Schulte, E. (1993). Tilings, Handbook of Convex Geometry, Vol. A, B, Amsterdam: North-Holland, pp. 899–932.
  • Steinitz, E. (1906). Über die Eulersche Polyderrelationen. Arch. Math. Phys. 11: 86–88.
  • Steinitz, E. (1922). Polyeder und Raumeinteilungen. Enzykl. Math. Wiss. 3(Part 3AB12): 1–139. (Geometrie).

Appendix

Table A1. Harmonic degree h¯ of uniform convex honeycombs, their duals, Poisson-Voronoi, Poisson-Delaunay and Hyperplane random mosaics, iterated foams and their duals.