ImageAnalStereol2014;33:39-54 doi:10.5566/ias.v33.p39-54 OriginalResearchPaper THE CHARACTER OF PLANAR TESSELLATIONS WHICH ARE NOT SIDE-TO-SIDE ¨ RICHARD COWAN1 AND CHRISTOPH THALEC,2 1School ofMathematicsand Statistics,University ofSydney,NSW2006,Australia; 2Faculty ofMathematics, Ruhr-UniversityBochum,Germany e-mail: rcowan@usyd.edu.au, cthaele@uos.de (ReceivedJuly23,2013;revisedDecember3,2013; acceptedDecember15,2013) ABSTRACT Thispaper studies stationary tessellations and tilings of theplanein which all cells are convexpolygons. The focusis onthe class oftessellations whichare not side-to-side. The character ofthesetessellationsis explored, with special attention paid to the relationship between edges of the tessellation and sides of the polygonal cells and to the combinatorial topology between the ‘adjacent’ geometric elements of the tessellation. Three newparameters, .0, .1 and .2 summing tounity,areintroduced.Thesecapturetheessenceof nonside-to-side tessellations andplay a rolein understanding the adjacency of sides and cells. Examplesillustrate the theory. Keywords: combinatorial topology, Delaunay tessellation, random tessellations, STIT tessellation, stochastic geometry, tilings. INTRODUCTION As discussed in the recent paper of WeissandCowan (2011),thefocus of attentionin most studies ofplanartessellations andtilingshasbeen the side-to-side case, where each side of a polygonal cell coincides with a neighbouring cell’s side. The studies of Cowan (1978; 1979)are early exceptionsin the random tessellation theory. Those studies, which also have relevance to the tiling literature, introduced a new parameter . . It quanti.ed one of the most important features of non side-to-side tessellations, namely the occurrence of a type of vertex not seen in the simpler side-to-side case: the so-called . -vertex. If a vertex has j emanating edges, there are j angles subtendedby these edges at the vertex. If one of these angles is equal to ., the vertex is called a .-vertex.A - vertex that is not a . -vertex is called a .-vertex. The parameter . is de.ned as the proportion of vertices which are .-vertices. Many properties of a non side-to-side tessellation can be expressed in terms of . together with another parameter, . , the mean number of emanating edges from the typical vertex. These fundamental parameters, which capture both topological and combinatorial aspects, satisfy thegeneral constraints 0.. .1; 3.. .6-2. , (1) asprovedin WeissandCowan (2011) andillustrated in Fig. 5a. There are, however, some entities of a combinatorial and/or topological nature which cannot be expressedas afunction of . and . . Soitisclearthat otherparameters ofthe non side-to-sidetessellation are important. In this paper, we investigate these issues, delvingintosomeofthe .nerstructureof tessellations which arenot side-to-side. Somemetricissuesarealso discussed and one parameter, the mean length of the typical tessellation edge,plays aprominent role. Fig. 1illustrates that ageneral random tessellation allows any shape or size of convex polygon to be a cell; furthermore it potentially allows any number and geometry of edges emanating from a tessellation vertex. Some models, however, might restrict the variation of thesefeatures somewhat. GEOMETRIC OBJECTS AND THEIR ADJACENCY A tessellation of the plane is a collection of compact convexpolygonal cells which cover theplane and overlap only ontheirboundaries. Theunionof the cell boundaries is called the tessellation frame. Each cellhas sides and corners, thesebeing respectivelythe 1-faces and 0-faces of the polygon, which lie on the frame. The union (taken over all cells) of the cell’s cornersis a collection ofpointsin theplane called the vertices of thetessellation. Thoselinesegmentswhich are contained in the frame, have a vertex at each end and no vertices in their interior are called edges of the tessellation. Two cells are said to be equal under motion if one can be found by translating and/or rotating the other. A tiling is a tessellation with a .nite number of equivalenceclassesunderthis ‘motion’relationship. Often a tilingseenin theliteraturehas no randomness, but we also permit tilings generated randomly. Most tilings use only a small number of polygons with congruent copies of these assembled to cover the plane. Our randomplanar tessellations(orplanar tilings) are assumed to be stationary – and also locally-.nite (avoidingpointsandline-segments‘accumulating’). The stationarity condition says that the geometric features are statisticallyinvariant under translation.To achievethiswith anon-randomtiling,such asin Fig. 6, one must ensure that the planar origin is uniformly distributed in the repeating sub-unit. Hybrid models (partlyrandom, partly non-random) can arise too, for example in the 2×1 tiling example in a later section; in that case, stationarity is created if the origin is uniformly distributed inside one of the original 2 ×2 squares. The tessellation’s primitive geometric elements, treated as compact domains, are the vertices, edges and cells. The sets of these elements are denoted by V, E and Z (for Zellen) respectively. These are the tessellation elements studied in the standard texts (Stoyan et al., 1995; SchneiderandWeil, 2008). In thispaper,however, other compactgeometric elements will be introduced and the set of these will also be denotedbyanupper–caseletter –forexample,thesets S and C of all sides and corners of cells, respectively. We note that, for those elements which are not primitive but are instead derived from a primitive element, then the set may indeed be a multi-set. For example, in side-to-side tessellations, every s . S equals another member of S, as be.ts the terminology side-to-side. Thismaybetrueforsome(butnotall) members of S in the non side-to-side case. Generic sets of compact geometric objects are denoted by X and Y. Subsets of the set X are denoted by X[·], with the contents of the [·] being a suitably suggestive symbolintroducedin an adhoc manner.For example, wedenotethe sub-class of .-verticesby V[.] and the subclass of . - -verticesby V[.- ]. Point processes and their intensities: The centroids of all members in a set of objects form a stationary point process on the plane, but this process might also have point multiplicity and, if so, it would notbe a simple pointprocess. DEFINITION 1: The intensity of objects belonging to class X is the intensity of the point process in R2 formedby centroids of the elements of X.It is denoted by .X. The scale of the tessellation is determined by one of the intensity parameters and we have chosen .V to play this scaling role. Our locally-.nite condition implies that .V is .nite. The other main intensities, reported in Weiss andCowan (2011), are expressedas followsin terms of .V and are also .nite: .. -2 .E = .V, .Z = .V, .S =(. -. ) .V, (2) 22 with .C = .S. Fromtheseidentities,wehave 2(. -. ) .S = .E , (3) . showing clearly the way this changes from .S = 2.E as we move awayfrom the side-to-side case whichhas . = 0. Metric parameters: There are many classes of line-segment that can be de.ned in a tessellation. The lengths of these segments together with the perimeters and areas of cells are the most obvious metric properties relevant to our study. The following notation applies. DEFINITION 2: If the class X comprises elements which are line-segments, we let lX be the mean length ofthese segments.Inparticular, l—E and l—S arethe mean edge length and mean side length respectively. We let — lZ be the mean cellperimeter and a—Z be the mean cell area. Itisknown,fromCowan(1978),that —aZ = 1/.Z = 2/(.V(. -2)) so —aZ isnotanewparameter. Theother ——— metric entities lE,lS and lZ are related to the frame intensity. The frame Y of the tessellation is the union of all edges and its intensity is the mean total length of Y ’s line-segments in any reference window W of ImageAnalStereol2014;33:39-54 unit area. The text of Stoyan et al. (1995) shows that tessellation models, the point process on this transect —— the frameintensity equalsboth .E lE and 1.Z lZ, so is a Poisson process and then the number KW(E) of 2 edges hitting a line-segment W of length l has the .E 2. ——— lZ = 2 lE = lE , (4) .Z . -2 — to which we add frame intensity = 1.SlS and the new 2 formula .E . ——— lS = 2 lE = lE . (5) .S . -. We see in Eq. 5 how the mean side length l—S departs from equality with the mean edge length l—E as . becomes positive (that is, as the tessellation departs from the side-to-side case). These metric entities are inter-related; in this paper we have chosen l—E as the principalmetricparameter. Window formulae and transects: Other properties of the tessellation observed in a window W, chosen without reference to the tessellation itself, are known (see formula (3.4) in Cowan, 1978). The most interesting of these are for convex W when the tessellationprocess Y is assumedisotropic(thatis,its geometricfeatures are statisticallyinvariant under any planar rotation). In this case, the number of edges of the tessellationintersectingW has expectation ( —) lE E KW(E)= Perim(W)+ Area(W) .E . (6) . Here we use the notation KW(X),de.ned as the count of X-type objects intersecting W. Also the number of cellsintersecting W has expectation E KW(Z)= 1+ (—) lE . -2 Perim(W)+ Area(W).E . (7) .. To these we now add the expected number of the tessellation’s line-segments of a given class X which intersectW: (lX ) E KW(X)= Perim(W)+ Area(W).X , (8) . as shownbyformula(6) of Cowan(1979), apaperthat deals withgeneralisotropicline-segmentprocesses. When W is a line-segment, of length l say, then each of the window formulae simplify, because Area(W)= 0 and Perim(W)= 2l. REMARK 1: With such a W and letting l ›., Eq. 6 indicates informally that the point process formed by the intersection of tessellation edges with a line transect (chosen without reference to — the tessellation) has intensity 2lE.E/.. In some property -. l (. l)ke P{KW(E)= k|l}= , k! where 2 — . = lE.E . . Inthese‘PoissonTransect models’,theBuffon-Laplace problem is effectively solved, giving a chance e-. l that a needle of length l thrown randomly onto the tessellation Y lies wholly within a cell of the tessellation. To understand this assertion, note that the thrown needle W is assumed to be an isotropic random set. Eqs. 6–8, with expectations taken of the perimeter and area of W, are valid when W is an isotropic random set evenif Y is notisotropic. Adjacency: The standard texts (Stoyan et al., 1995; SchneiderandWeil, 2008) discuss only the primitive elements V, E and Z. Their notation which works well in that restricted context is unsuitable when other object classes like S or C are introduced, because then object classes are not uniquely de.ned bytheirdimension.For example,thetextbooknotation .1 used for the intensity of edges E (because edge have dimension one) cannot be used when there is another object class, sides S, whose elements alsohave dimension one. This notational de.ciency becomes serious for tessellations in R3 (WeissandCowan, 2011)but, even in R2, we .nd advantage in adopting the notation used in WeissandCowan (2011). We recommend to the reader the .rst two sections of their paper, as itprovidesfurtherdiscussion and motivation for the notation. DEFINITION 3: An object x . X is said to be adjacent to an objecty .Y if either x .yory .x.For any x . X, the number of objects of type Y adjacent to x is denoted by mY(x). For a random tessellation we de.ne µXY as the expected value of mY(x) when x is the typical member of X. Formally, we write µXY := EX(mY(x)), where the symbol EX (and the probability measure PX on which it is based) indicate that we are dealing with the typical element of type X(Stoyanet al.,1995;WeissandCowan,2011). The second moment EX(mY(x)2) of the number of type Y objects adjacent to the typical X object is written as µXY(2). Many features of interest can be expressed as an adjacency. For example, µSE is the expected number of edges adjacent to a typical side(thatis, the mean number of edges in a typical side). This is one of the quantities expressible solely in terms of . and . (Weiss andCowan,2011): . µSE = , (9) . -. which clearly equals1in the side-to-side case. The nine values of µXY where both X and Y are primitive elements, thatisX and Y .{V, E, Z}, can all be expressed solelyin terms of . (Stoyan et al.,1995; WeissandCowan,2011). Themostimportanttwocan bepresented asfollows. 2. µZE = µZV = , (10) . -2 which were .rstprovenforthegeneral casein Cowan (1978;1980)and Mecke(1980), thoughtheyhadbeen mentioned withoutproof andin restricted cases earlier. In the side-to-side case, the right-hand side of Eq. 10 also equalsthe expected number of sides(or corners) of atypicalcell –buttheseentitiestakeadifferentform in the non side-to-side case, as we discuss in a later subsection. When X and Y arebothprimitive-element classes, ithasbeen shownin Mecke (1980), WeissandZ¨ahle (1988)and LeistritzandZ¨ ahle (1992)that .XµXY = .YµYX , (11) and thisidentity alsoholds when either X or Y orboth are classes of faces ofprimitives;Moller’s Theorem5.1 (Moller,1989)providestheproofofthis extension.As an example, µES.E . µSE == , .S . -. proving Eq. 9 with the use of Eq. 3 and the obvious fact µES = 2. In concluding this subsection, we note that . and . can be expressed using the adjacency notation; . = µVE and . = µ ., the expected number of VS ‘side-interiors’ adjacentto atypical vertex(wherethe interior of a side, or indeed of any object x of lower dimension than the space ofthe tessellation,isde.ned using the relative topology on x). Also X°denotes the class comprising the relative interiors of objects in class X. For brevity we drop the word ‘relative’ in the sequel; ‘interior’means ‘relativeinterior’. Faces ‘owned by’ other objects: As proved in Cowan (1978; 1980) and used in applications (CowanandMorris,1988;Cowanand Tsang,1994), 2(. -. ) .1(Z)= .0(Z)= , (12) . -2 where .1(Z) and .0(Z) are the mean number of sides and corners of the typical cell. This is an ownership concept rather than an adjacency;not all sides that are adjacenttoacellbelongtoit. The . notationin Eq. 12 willbegenericallyde.ned shortlyinDe.nition4, after wediscuss an application. Eq. 12 has application to the type of question common in the literature on tilings. “Can we tile the plane using only convex pentagonal tiles?”. Obviously we can, there being examples using congruent copies of some particular pentagons (Gr¨unbaumandShephard, 1987). But Eq. 12, combined with Eq. 1, tells us that we certainly can’t 1 do soif . > 2, even if we use convex pentagons of differing sizes and shapes(because then . would be 1 < 3). The bounding case, with . = 2 and . = 3, can be realised so easily – start with the hexagonal lattice (made stationary in R2 by placing the origin uniformly distributed within a hexagon) and divide every hexagon into two pentagons with a chord, ensuring that chord-ends never meet – that we might expecthigher . values arepossible.But they are not! DEFINITION 4: Let X be a class of convex polytopes, all members of which have dimension i. For j < i, we de.ne nj(x) as the number of j-faces of a particular object x . X. De.ne . j(X) := EX(nj(x)), the expected number for the typical X­object.Wede.neXj, j< i, asthe class ofobjects which are j-dimensional faces (j–faces) of some polytope belonging toX. We shallusethis notationintheplanar case mainly when j = 0 and i = 1. For example, E0 is the class of edge-termini and S0 the class of side-termini. Also Z0 and Z1 are the classes of cell corners and sides respectively; also known by the labels C and S which we retain for convenience, except when de.ning the important entities, .1(Z) and .0(Z). The disparity between the number of edges adjacent to a cell z (that is, on the boundary of z) and the number of sides owned by z provides another measureofdeparturefromtheside-to-sidestatus. This suggested measureis µZE -.1(Z) which,from Eq. 10 andEq. 12, equals2. /(. -2). This measure which we call the cell boundary disparity lies in the range [0, 2]; the upperboundoccursin a number of models, notably inthe STIT model which wediscusslaterinthepaper. OTHER PARAMETERS AND THE EQUALITY RELATIONSHIP Two additional parameters: Sometimes the typical element of a classgives abiassed sampling of ImageAnalStereol2014;33:39-54 another type of element. Consider µCE, the expected number of edges adjacent to a typical cell corner. The typical sampling of the corner gives a number­of-edges-emanating bias to the sampling of a vertex, and this leads to the introduction into the formula of µVE(2), the second moment of the ‘number of edges emanating from the typical vertex’. As shown inWeiss andCowan (2011), µVE(2) -.µV[. ]E µCE = , if . > 0, (13) . -. whilst µCE = µVE(2)/. if. = 0. Eq.13alsointroduces µV[.]E, the expectation ofthe number edges emanating from the typical .-vertex, an entity de.ned when . > 0. For brevity, we denote it by .. ; we also use .- . for µ- , though this is not another new parameter V[. ]E because . .µVE = . µV[. ]E + (1-. )µV[ - . ]E .. .. + (1-. ).- . . (14) REMARK 2: Interestingly, whilst we see in Eq. 1 that . (which . µVE) is bounded above, examples show that .. and .- can be arbitrarily large. For example, . it is easy to construct a tessellation with very few .­vertices with each .-vertex having n edges, n being arbitrarily large. Another example is available, with non-. vertices being rare but emitting n edges, where nislarge(details omitted). D WeissandCowan (2011) have used the four parameters (. and . , together with the additional parameters, µVE(2) and .. ) to give formulae for all relevant intensity parameters .X and for all but three of the forty-nine µXY entities between the seven classes of elements that they study: X and Y both .{E,V, Z, E0,C, S, S0}. This suggests that three more parameters are required, and we could choose to use thethree missing entriesin WeissandCowan (2011), µSZ, µZS and µSS –butactuallytwo suf.cebecause µSZ and µZS are related (via Eq. 11). There are however more natural choices, as we shall see later in this section. The equality relationship: The relationship between edge and side, and the cell ‘owning’ the side, will occupy much of our attention in this paper. The complications in their adjacency relationship is demonstrated in Fig. 2, perhaps explaining why formulae for the missing trio have not yet been found for the general non side-to-side tessellation, nor for any model until recently. In the side-to-side case,mS(e)= 2for everye .E. Despite the added complication seen in Fig. 2 which arises in the non side-to-side case, this identity still holds–becauseadjacencyinvolvesthesubset concept; every e . E is a subset (.) of two sides. To better capture how edges and sides relate, we need to focus on another relationship, equality. DEFINITION 5: Suppose the objects in class X havethesamedimensionasthoseinclassY. Thenthe number of objects of type Y equal (as a setin R2) to some x .X is denoted by the random variable mY(x). Wede.ne µ XY as EX(mY(x)). Itistheloss ofequality of E and S, ratherthantheir loss of adjacency, that happens when a tessellation is not side-to-side. An edge is not always equal to the side of two cells, that is, mS(e), e . E may not always equaltwo;ittakesthe values0, 1or2 randomly. Depending on this value, the class E can be divided into sub-classes E[0], E[1] and E[2]. Fig.2. The shaded regionis a cell; one ofits sidesisthe horizontal line-segment which bounds it below. This side shas a varying number mE(s) of edges contained within it, as shown. The value of mS(s), the number of sides adjacenttoit(the countincluding sitself), also varies as shown. Weintroduce,forthetypicaledge,theprobabilities .0, .1 and .2 for these three outcomes. Naturally, .0 + .1 + .2 = 1, and = .1 + 2.2 . (15) µES — When needed, we use symbols l—E[0],lE[1] and l—E[2] for the expected lengths of typical edges of the three sub­ ———— classes; obviously, .0lE[0]+ .1lE[1]+ .2lE[2]= lE. We now consider the random variable mE(S), the number of edges equal to a typical side. It is binary, taking only the values in {0, 1}. So, using Eq. 3 and Eq. 15, PS{mE(s)= 1}= µ SE .E . (.1 + 2.2) = = . (16) µES .S 2(. -. ) Also usedin this expressionis the analogue of Eq. 11; such analogues existfor all symmetric relations. Another descriptor of ‘not being side-to-side’ is , the expected number of sides equal to a typical µ SS side. Thisisderived asfollows: 2.E[2] .2. µ SS = 1+ µSE[2]= 1+= 1+ , (17) .S . -. using µE[2]S = 2 andEq. 11. The missing mean adjacencies in terms of the epsilons: We now show that the three missing mean adjacencies, µSZ, µZS and µSS, can be expressed in terms of . , . , .0, .1 and .2. THEOREM 1: The three mean adjacencies missing in the table of forty-nine such entities in Weiss andCowan (2011)are . (.1 + 2.2) µSZ = 1+ , (18) 2(. -. ) 2(. -. )+ . (.1 + 2.2) µZS = , and (19) . -2 . µSS = 1+(1-.0) . (20) . -. PROOF:Note that mZ(s)= 1+ mE(s), for alls .S, so µSZ = 1+ µ SE and Eq. 18 follows by applying Eq. 16. Furthermore, via Eq. 11, µZS = .S µSZ/.Z 1 and this equals Eq. 19 using .Z = (. -2).V and 2 .S =(. -. ).V. ToproveEq. 20, we start with asubtle expression for mS(s), the number of sides adjacent to aparticular side s (seeDe.nition3).For allsides s, mS(s)= 1+ mE(s) -mE[0](s) . (21) Theproof ofthisis essentiallygivenbythediagramsin Fig.2,treatingthehorizontalline-segmentthatbounds the shaded cell below as our particular s. Essentially, the six diagrams present all of the complexity that a neighbourhood of s mighthave.It readilyfollowsfrom Eq. 21that µSS = 1+ µSE -µSE[0] .E .E[0] = 1+ µES - µE[0]S usingEq. 11 .S .S .E .E[0] .E = 1+ µES - µE[0]S .S .E .S 2.E () = 1+ 1-.0 .S . = 1+(1-.0) , . -. usingthede.nition of .0,thefactthat µES = µE[0]S = 2 andEq. 3. Therefore,identityEq. 20 hasbeenproved and the theorem’sproofis complete. D We consider that .0, .1 and .2 capture the essence of ‘not being side-to-side’, and so we adopt them as fundamental parameters instead of µSZ, µZS and µSS, which are not asimmediately relevanttothe concept of side-to-side. Thus the topological parameter setof our choice now becomes {. , . , µVE(2), .. , .0, .1, .2}, with .0+ .1+ .2 = 1.Our scaleparameter.V has relevance too,butitdoesn’tin.uencethe combinatorialtopology of our system.Nordoes our main metricparameter l—E have topological relevance. EXAMPLES A 2×1 tiling: As a relatively simple learning example, consider the square lattice made up of 2×2 squares. Each square is then tiled by two 2 ×1 tiles, with random orientationfor the long axis of these two tiles(verticalorhorizontal with equalprobability). The bold lines in Fig. 7 illustrate the construction. Find all the parameters of the tessellation — to reinforce the notation andthe relationshipsbetween theparameters! Looking at the typical cell, clearly —aZ = 2, l—Z = 6 and .1(Z)= 4. Therefore .Z = 1/a—Z = 1 and, from 2 9 Eq. 12, . = 4-. . Note also that µZV = 2, because on one side (and only one) of each tile there is an extravertexadded withprobability 1. Therefore,from 2 18 2 Eq. 10, . = . Then . = 4-. = . Now we can 55 59 write .V = 2.Z/(. -2)= and .E = ..V/2 = , 88 1 usingEq. 2.Also write .V[.]= ..V = .Itis obvious 41 that .0 = 0 and that .E[1]= 2.V[. ]= . Therefore 245 .1 = .E[1]/.E = == and .E[2]= 9, .21-.0 -.19 — .2.E = 5 . Thelineintensityis 1lZ.Z, which equals 3; 822— 4 thelineintensityis also l—E.E, so lE = 3.As obviously ——— 4 lE[1]= 1, wederive lE[2]=( l—E -lE[1].E[1])/.E[2]= 3. Finally .. = 3 and µVE(2)= 9. + 16(1-. )= 66 . 5 The STIT model: This tessellation, perhaps the best-known model that is not side-to-side, was .rst studiedby Nagel andWeiss (2003;2005), andlater by them in collaboration with Mecke (Mecke et al., 2007; 2011). Other recent studies of the planar STIT tessellationareby SchreiberandTh¨ ale (2010; 2013) and Cowan (2013). In this model, drawn in Fig. 3a, all vertices are .-vertices with three edges emanating, so . . µVE = .. = 3, µVE(2)= 9 and . = 1. Forty-six adjacency entities can now be evaluated from WeissandCowan (2011),the mostinterestinginthe context of the current paper being µSE = . /(. - 3 . )= and µZE = 2. /(. -2)= 6. There is also the 2 ImageAnalStereol2014;33:39-54 important . entity, the mean number of sides for the typical cell: 2(. -. ) .1(Z)= = 4. . -2 So the cellboundarydisparity is2. The results given above for the STIT model are not new (see Nagel andWeiss, 2005), but, until the recent paper (Cowan, 2013), STIT results ——— for .0, .1, .2,lE[0],lE[1],lE[2], µSZ, µZS and µSS were unknown. From this recent paper, we state the following values: .0 = 2 (2log2-1) .0.25753, 3 2 .1 = 3 (5-6log2) .0.56075, 1 .2 = 3 (8log2-5) .0.18173, 3(3-4log2) ——— lE[0]= lE .0.883 lE , 2(2log2-1) 3(8log2-5) ——— lE[1]= lE .0.972 lE , 2(5-6log2) 3(3-4log2) ——— lE[2]= lE .1.251 lE . 8log2-5 J 1 Here, l—E = 2. /.V. From these values, together 3with Eqs. 15–19 from the current paper, we have the following results: 4 µ ES = .1+ 2.2 = 3log2.0.9242, PS{mE(s)= 1}= log2.0.6931, µ SE = .2. = 1+= 4log2-3 .1.2726, µ SS 2 . -. µSZ = 1+ log2.1.6931, µZS = 4+ 4log2.4.9242. 3 AlsoderivedinCowan (2013)is 7 -2log2.2.1137, µSS = 2 together with full distributions for many of the STIT adjacency relationships. It is readily seen that µSS calculated by the new formula, Eq. 20 in Theorem 1, agrees with the resultin Cowan (2013). Divided Delaunay: Start with a stationary and isotropic Delaunay tessellation D0 based on a planar Poisson point process with intensity . (the dots in Fig. 3b). This tessellation is illustrated by the solid line segments in the .gure, connecting ‘neighbouring’ Poissondots(seetheformalde.nition in SchneiderandWeil (2008)). This tessellation is side-to-side, so has . = 0. Also, since all cells are triangles, .1(Z)= 3 and therefore . = 6 from Eq. 12. Thesecond moment, µVE(2),introduced above, is known in the form of a complicated multiple integral which evaluates to be 37.7808 approximately (Heinrich andMuche, 2008). Obviously.V = .; then 11 usingEq. 2 weget .E = 2..V = 3. and .Z = 2 (. - 2).V = 2.. Also, because .E[2]= .E, it is clear that .2 = 1.Note that l—E = 32/(9. . . ) (Miles,1970). (a) (b) Fig. 3. (a) A realisation of the STIT model within a rectangular viewing window. (b) The ’divided Delaunay’ model. The chords are shown as dashed lines. In each of D0’s triangular cells we independently choose a vertex (each equiprobable) and construct a chordfrom that vertex to a uniformlydistributedpoint on the opposite side of the triangle(see thedottedline segments in Fig. 3b). We label the new tessellation D1. Further iteration using the same random division rules yields D2, D3, ..., each being a tessellation with only triangular cells. Using superscripts (n) for the parameters of Dn (even when n = 0), we note that if n .1, (n)(n-1)(n)(n-1)(n-1) . = 2. , . = . + . , ZZ V[.] ZV[. ] (n)(n-1)(n-1)(n)(n-1)(n-1) . = 2. + . , . = . + . , EZE VZV . (n) = 6-2. (n), the last of these identities arising from Eq. 12 (and holding for any tessellation which has only triangular cells). These four difference equations are readily solved togive (n)(n) . = 2n+1. , . =(2n+2 -1). , ZE (n)(n) . =(2n+1 -1). , . = 2(2n -1). , VV[. ] andthese solutionsyield aformulafor . (n) whichleads to . (n): (n) . V[. ] 2(2n -1) . (n) == (n) 2n+1 -1 .V 2n+2 -1 . (n) =. = 6-2. (n)= 2 . 2n+1 -1 Thusthe cellboundarydisparity is1-2-n , which rises from zero to alimit of1 as n increases. (1)(1) 2 So for D1, . = 3., . = 7. , . (1)= and VE 3 . (1) 14 = 3 . Also for D1 the calculation of the epsilons is easy because D0 is side-to-side and therefore has only E[2] edges. An edge from D0 is divided into three segments withprobability1/9,intotwo segments with probability 4/9 and remains unchanged with (1)(0) 4 (0) 10 probability 4/9. Thus . = . + 1· . = ., E[2] Z 9E[2] 3 after allowing for the unchanged edges which remain as type E[2]. Furthermore, . =(1) 1 (0) 1., as one . = E[0] 9E 3type-E[0] edge arises when an original edge is hit by (1) 41 (0) 10 two chords. Lastly, . =(2· + 2· ). = .. E[1] 99E 3 (1)(1)(1) Therefore, using .j = . /.E , E[ j] (1) 1 10 10 . = , .1 (1)= , .2 (1)= . 0 21 2121 Then,usingTheorem1, 11 99 19 (1) (1) (1) µ= , µ = , µ= . SZ ZS SS 6 28 9 Additionally,from Eqs. 15–17, (1) 10 (1) 5 (1) 14 µ , µ , µ . ES = SE = SS = 769 (1)(1) For D1, one can also show that .. = 3 and µ= VE(2) 58 16 + ×37.7808 . 28.833. Calculation of various 9 27 entities for Dn when n > 1, is more dif.cult and will bedemonstratedlaterin the next section. We close this example for now, noting that some limiting topological properties of repeatedly divided triangular cellshavebeen addressedin Cowan (2004; 2010)whilst the three-dimensional version ofdividing cellsin aDelaunay tetrahedral tessellation is analysed in Weiss andCowan (2011). FURTHER CLASSIFICATIONS OF EDGES AND EDGE-TERMINI We have seen that a typical edge may be equal to a variable number of sides, 0, 1 or 2. Is this variability also evident when we observe atypical edge-terminus? A classi.cation of edge-termini: We can sample a typical edge-terminus, that is a typical e0 . E0, by .rst sampling a typical edge e .E and then randomly choosing one of its termini. Having done this, we can observethe number of side-termini equaltothe chosen edge-terminus – the count restrictedto termini of sides s such that e .s. We see that such an e0 is equal to either 1 or 2 side-termini. So each terminus can be sub-typed as E0[1] or E0[2] based on this idea. Introduce the temporary notation . for the expected number of such sides having the typical edge-terminus as an 0­face. Note that .E0. = 2.S, so . = 2(. -. )/. . This evaluatesto 4inthe STITmodel and 12 intheDivided 37 Delaunay D1 model. Also, it is easily shown that .E0[1]= 2.V[. ]= 2..V (as there are twoE0[1] termini at every .-vertex and none at vertices that are not .­vertices) and that .E0[2]= .E0 -.E0[1] =(. -2. ).V. Thus 2. PE0{e0 .E0[1]}= , . 2. PE0{e0 .E0[2]}= 1- . (22) . Another classi.cation of edges: An edge can be classi.ed by the type of its termini. One potentially useful method might be as follows: an edge is of type [ j], j.{zero, one, two}if exactly jof its termini are of type E0[2]. So this gives a new breakdown of E into E[zero], E[one] and E[two], a verbal annotation which avoids confusion with the previous numeric breakdown, E[0], E[1] and E[2]. We note that E[2] . E[two], so PE{e .E[two]}= .2. We also note that E[0] . E[zero] and E[one] . E[1]. Also each E[1] edge can be labelled, ‘zero’or ‘one’ fromthesecond classi.cationmethod.(see Fig. 4). This means that the edges are now classi.ed into four types – the original E[2] and E[0] plus the two components of E[1], namely E[1& zero] and E[1& one] which we abbreviate as E[10] and E[11] respectively. We also break .1 into two terms, .10 and .11, with .1 = .10 + .11. ImageAnalStereol2014;33:39-54 E[2] E[1] E[0] E[two] E[one] E[zero] Fig. 4. In each picture, focus attention on the horizontal edge whose termini are both in view. This edge lies in the categories shown schematically below eachpicture. Both methodsof classi.cationareshown. From the method stated above for the sampling of a typical edge-terminus, wehave PE0{e0 .E0[2]}= PE{e .E[two]} 1 + PE{e .E[one]} 2= .2 + 1 PE{e .E[one]}. (23) 2 UsingEq. 22 andEq. 23,we .nd that 2. .11 = PE{e .E[one]}4. = 2(1- . -.2), (24) .10 = .1 -.11 = . -.1 -2.0 . (25) For the general planar tessellation we see that, although we now have a .ner classi.cation of edges, no extraparameteris needed; .10 and .11 are not really new as they can be calculated from the parameters of our .rst classi.cation. The .ner classi.cation does, however,play a rolein some situations(as seenlater in this section). Linking .2 and . : Eqs. 24 and 25 provide inequalities which link .2 and . . Writing Eq. 24 as 1 .2 = 1-2. /. - .11, we can create an upper bound 2for .2 in terms of the ratio . /. . Similarly, Eq. 25 establishesalowerbound. Theseboundsarepresented belowinEq. 26andillustratedin Fig. 5b. 4. 2. 1- . (26) + .0 ..2 .1- .. Note that (.2 = 1)=. (. = 0) from the upper inequality and (. = 0)=. (.2 = 1) and (.0 = 0) fromthelowerinequalityandthefactthat each epsilon . [0, 1]; so (. = 0) and (.2 = 1) are equivalent, as is intuitively obvious. The earlier examples revisited: In the STIT 4 example, .11 = (3-4log2) . 0.3032 whilst .10 = 3 2 (2log2-1) which happens to equal .0. Note also 3 — that l—E[10]= lE[0], proved by the methods in Cowan ——— (2013), sotherefore lE[11]=(.1lE[1] -.10 lE[10])/.11 = — 3(3log2-2)l—E/(3-4log2)= 1.048lE. ..2 6 1 3 . 2. /. 1 1 (a) (b) Fig.5. (a)Thepermittedrangefor (. , . ) asdescribed in the inequalities of Eq. 1. (b) The permitted range for (2. /. , .2) for a given value of .0, taken from the inequality Eq. 26. Note that .10 = 0 and .11 = .1 = 10 in the 21 Divided Delaunay tessellation D1, as expected from thedescription ofthat model(wheretype E[10] is an impossibility). In the 2×1–tiling, none of the E[1]–edges are of type E[10], so .10 = 0 and .11 == 4. Thus edges .19are either of type E[2] or type E[11], a feature that allows uslater to compute theproperties of this model combined in superposition with any isotropic model. — Obviously, l—E[11]= lE[1]= 1. The example in Fig. 6: An example which demonstrates .10 and .11 is seen in Fig. 6; it is 19 described andpartially analysed(yielding . = and 6 5 . = 6)in the .gure’s caption. The area of the shaded region is 32 so, because of the 7 cells, 19 edges and 12 vertices associated with this area, .Z = 7 , .E = 32 19 3 32 and .V = 8. Furthermore, of the 19 edges, 4 are type E[0], 10 are E[1] and 5 are E[2]. Therefore .0 = 410 5 10 , .1 = and .2 = . Eq. 24yields.11 = 2(1- - 1919 1919 58 2 )= , so .10 = from Eq. 25. This agrees with 191919 the observedbreakdown of type E[1] into sub-types:8 being E[11] and2being E[10]. Fig. 6 with each cell divided once: To illustrate the use of the classi.cation of edges as shown in Fig. 4, we consider the tessellation that arises when each cellofourrectangulartessellation(shownin Fig. 6) is independently divided by a chord – one which is uniformly randominthe set of all vertical orhorizontal chords of the cell, thus retaining rectangular cells. Fig.6. A tessellation based on congruent copies of the region shown in dark shading arranged to cover the plane.Itis made stationarybyensuring that the origin is uniformly distributed within the dark region. This region measures 8×4 and comprises 7 rectangular cells whose side lengths are of integer length, either 1, 2 or 4 units. The heavy lines within the dark region comprise19 edges and there are12 vertices within the region not counting those on its northern and eastern boundary(asthese are countedin other copies of the region).Ten ofthe12 vertices are .-vertices(each with 3 emanating edges) and the remaining two are not . ­vertices(eachhaving4 emanating edges).So . = 19 6 and . = 5 . The white patches, each containing two 6 cells, are explainedlaterin the text. Consider .rstlythetop-leftwhitepatch;it contains a4 ×2 upper cell and a 2×2 lower cell, separated by an edge oflength2(whichhappenstobe oftype E[10]). Conditioning on the geometry of the patch, the chance that the separating edge is hit by the upper cell’s chordis2 times the edge’slengthdividedby the perimeteroftheuppercell,namely 1.Forthelower 3cell,theconditional chanceis 1.Giventhegeometry 2of the patch, these hitting events are independent. So the probability (given the patch geometry) that the 1 separating edge is hit by 0, 1 or 2 chords is 1 , and 1 32 6 respectively.Repeating the calculationfor thebottom­ right patch, where the separating edge is also of type 1 E[10], wegetprobabilitiesfor0, 1or2hitsof 3 , and 102 1 5 respectively, conditional on that patch’s geometry. Any hit is independently uniformly distributed along the separating edge. Asthesetwopatches(andtheir equally-prevalent copies throughout the plane) contain the only type E[10] edges, we can say that the chance that a typical 3 1 E[10] edge receives 0, 1or2hitsis 1( 1 + )= 19 , 23 10602 1 and 1( 1 + )= 11 respectively.An E[10] edge e which 26560 is nothit remains of type E[10] andhit twicebecomes one E[10] plus two E[0] edges. Hit once by the chord in the cell whose side s equals e,itbecomes two E[10] edges(theprobabilityhereis 19 ).ItbecomestwoE[0] 60 edges if the hit comes from the cell whose side s .e 11 (probability 60). The third row ofTable1 shows the resulting edge­typesproducedfrom thepossiblehits on E[10] edges. The same exercise can be repeated for the eight edges that are of type E[11]. The post-division edge­typesdifferfrom thosein the E[10] analysis(seeTable 1), emphasising the need to break the type E[1] into itstwoparts. Thehitprobabilitiescanbefoundforthe typical E[11] edge:nohits, 103 ;twohits, 1;onehit 18018 19 29 with s = e, ;onehit with s .e, 90180. For the .ve E[2] edges, Table 1 presents the resulting edge-types and a calculation shows that there will be 0, 1 or 2 hits of the typical E[2] edge 8 11 34 with probabilities , and respectively. The 7525 75 probabilities of 0, 1 or 2 hits of the typical E[0] edge 5 1and 1. are , 83 24 Table 1. Giventhe edge-typegivenin column one,the Table shows the types of edges that result from j hits by chords, j = 0, 1, 2. For example, a [0]-edge hit by 2 chords is subdivided into three edges; either all three willbetype [0] orthere willbetwo oftype [10] and one of type [0]. Given j = 2, the alternatives linked by the word ‘or’ are equally likely in all examples, but when j = 1 the alternatives ‘s = e’ and ‘s . e’ will have example-dependentprobabilities(see text). type j= 0 j= 1 j= 2 [2] [2] 2[11] (2[11] + [0]) [11] [11] s = e ([11] + [10]) or s . e ([11] + [0]) ([11] + 2[0]) or ([11] + [10] + [0]) [10] [10] s=e 2[10] or s.e 2[0] ([10] + 2[0]) [0] [0] ([10] + [0]) 3[0] or (2[10] + [0]) From these details and the information in Table 1, we can write down the intensity of the various edge typesafterall cellshavebeendivided.Using *forthe post-division results and no label for the pre-division terms, wehave thefollowing: ImageAnalStereol2014;33:39-54 8 113 . * = .E[2]+ .Z = , E[2] 75480 . * 2( 11 34 127 = + = , E[11] 25 75).E[2]+ .E[11] 240 . * ( 19 1 1 19 11 = + × ).E[11]+( 19 + 2× + E[10] 90 21860 60 60).E[10] 1 511 +( 1 + ).E[0]= , 3 242880 34 1 11 . * = .E[2]+( 29 + ).E[11]+ 2( 11 + E[0] 75180 1260 60).E[10] 1 887 +(1+ 2× ).E[0]= 482880 . 5 Adding the four intensities above yields .E * = ,a 4result which conforms with the simpler equation, 19 75 . * = + 3× = . E = .E + 3.Z 32 32 4 Note that . * = . * + . * = 407 . Also, the E[1] E[11] E[10] 576epsilons follow: .rstly . * = . * /. * = 113 , then 2 E[2]E 600407 887 similarly .1 * = and .0 * = . For completeness, 720 3600 . * 13 3 = .V + 2.Z = and . * = .V[.]+ 2.Z = V 16 V[. ] 4, 40 12 implying that . * = and . * = 13 13. REMARK 3: We note that the mathematics of this example is unchanged if, instead of using only horizontal and vertical chords, those which are distributed uniformly random (UR) on the set of all chords are used. The probability, given the cell’s perimeter b, that a chord hits an edge of length l is still 2l/b. D REMARK 4: Table 1 is universal; it holds for any tessellation and any mechanism for determining the dividing chords. So the point of our example is this: for any tessellation all four epsilons, .2, .0, .11 and .10 are essential inputs to the calculation of post-division structure. Another input is also needed: the probabilities of 0, 1 or 2 hits of the separating edge for each edge type. These probabilities were simply calculatedin our example,but couldbe ratherdif.cult to .ndingeneral. D The D2 iterate of the Delaunay: To illustrate Remark 4, we consider again the Divided Delaunay tessellation. We note that the .rst iterate D1 has no E[10] edges, .10 = 0 being implied by the equality of .1 and .11. In the second iterate D2, however, we see from Table 1 that this type occurs — E[10] can arise from the division of either E[11], E[10] or E[0] types. The relevant recurrences, after calculation of thehitprobabilities and application ofTable1(details omitted), are: (2) 4 (1)(1) 148 . = . + . = . , E[2] 9E[2] Z 27 (2) 10 (1) (1) 190 . = . + . = . , E[11] 9 E[2] E[11] 27 (2) 11 (1)(1) 11 (1) 121 . = . + 0×. + . = . , E[10] 36E[11] E[10] 36E[0] 108 (2) 1 (1) 7 (1)(1) 37 (1) 49 . = . + . + 0×. + . = . . E[0] 9E[2] 36E[11] E[10] 36E[0] 36 (2) From these we get the basic epsilons for D2: .= 148 (2) 881 (2) 49 ; . = ; .= . One can also show that 4051 16200 540 (2) 29 (2) 262 256 . = and µ= + ×37.7808.26.7617. . 9 VE(2) 27 567 We do notpresent results for Dn, n > 2 as analysis of thehitprobabilitiesbecomes very complicated. EXAMPLES OF NESTING AND SUPERPOSITION These two operations which can be applied to a pair oftessellations arede.ned asfollows. DEFINITION 6: Consider two tessellations with frames Y1 and Y2;the superposition is the tessellation with frame Y = Y1 . Y2. Object classes of Y are denoted by V, E, Z, S, ..., as usual, and those belonging to tessellation Y j, j= 1, 2, are denoted by V( j), E( j), Z( j), S( j) , ....A similar superscriptis usedfor . ( j), . ( j) parameters of Y j (for example, , ...), except ( j) when such useis redundant(asin . , whence either E( j) ( j) .or . suf.ces, thelatterbeing easier to read). E( j) E In this section, Y1 and Y2 are assumed independent; an exception to this is given in the next section. DEFINITION 7: To describe nesting, we again start with a tessellation frame Y1. Also we have available the distribution of the independent frame Y2, allowing us to produce independent replicates of Y2 when required. Then, for each closed cell z of Y1, we independently generate a tessellation Y2(z) distributed as Y2 and add Y2(z) .z to Y1. Thus we create a tessellation Y equal to Y1 plus all ‘nested components’ inside the cells of Y1, that is,  Y = Y1 . (Y2(z) .z) (Maier andSchmidt, 2003; zNagel andWeiss,2003).Notationisthe same asthatin De.nition 6, with the comment that the superscripted parameters and object classes when j = 2 refer to Y2 and do not have a clear de.nition for Y2(z) .z when z .Z(1) . Manyresearchershavediscussedthe superposition and nesting of two tessellations, presenting formulae for parameters like .V and .E in the resulting process in terms of the parameters for each of the original tessellations (Santal´o, 1984; Mecke, 1984; WeissandZahle¨, 1988; MaierandSchmidt, 2003; Nagel andWeiss,2003;2005).An assumption needed for reasonablypleasantformulaeis that atleast one of Y1 or Y2 should be isotropic. We too can reproduce those results very simply from Eq. 6 — and do so in the Appendix, taking Y2 as the isotropic structure (an assumption which prevails in this section). The formulaethatresult are asfollows, using(S) and(N)to mark the superposition and nesting cases respectively. . (1)(2) 4 (1)(2)(1)(2) . —— . . + . + ll .. (S) EE . EEEE .E = (27) . (1)(2) 6 (1)(2)(1)(2) . l—l—.. (N) .E + .E + EEEE . . 2 (1)(2) (1)(2)(1)(2) . —— . . + . + ll .. (S) VV . EEEE .V = (28) . (1)(2) 4 (1)(2)(1)(2) . l—l—.. (N) . + . + VV . EEEE We have a greater interest, however, in the effects of these operations on parameters like .V[.], . and . j.Santal´o(1984),who .rstanalysedtheeffectsof superposition – and others cited above who extended his analysis and introduced nesting – were not concerned with these parameters. In the theory and examples given below and in the Appendix, we focus on .V[. ], . and . j, j= 0, 1, 2, while drawing on the known results Eq. 27 andEq. 28. Theparameters .V[. ] and . : Forsuperpositions itis easily seen that the only . -verticesin Y are those that were . -vertices in the initial tessellations Y1 and Y2; no new .-vertices are created by the intersection ofthe twoframes.Onthe otherhand, nesting produces new .-vertices created by the intersection of Y1 with  (Y2(z) .z) whilst also retaining the original . ­ z vertices of Y1 and ofthe nested replicates of Y2. These remarks on .-vertices lead(with the help of Eq. 31 in theAppendix) to thefollowingformulae. . (1)(2) .. + . (S) . V[.] V[.] .V[.]= (29) . (1)(2) 4 (1)(2)(1)(2) . —— . + . + ll.. (N) EEEE V[.] V[.] . Theparameter . isgivenby .V[. ]/.V. Edge-types: Inbothcontexts, we saythat an edge in the resulting tessellation frame Y is of Y1-genesis if it is a subset of the Y1 frame. Otherwise, it is of Y2-genesis. It is important to note that an edge of Yi ­genesis might not be an edge of Yi, but only a subset of one. REMARK 5: If Y2 is side-to-side, all of the edges in Y of Y2-genesis will be of type E[2], whether Y is a superposition or a nesting. If Y2 is not side-to-side, results about edge-types are usuallyless amenable. Asuperposition example: The (2×1)–tiling seen above plays the role of Y1. Its superposition partner Y2is ourisotropicDelaunaytessellationD0, chosento have parameter . =(3. /8)2 . 1.388 so that . (1)= E (2) . in conformity with Fig. 7. Therefore, in this E example, Y2 is side-to-side and Y1 has no edges of types E[10] or E[0], a feature which enables an easy analysis. Fromthisearlieranalysis,weknowthat (1) 5 (1) 9 18 . (1) .V = , .E = , = , 885 (2) 9. 2 (2) 27. 2 . (2) .V = , .E = , = 6, 64 64 and 4 12 (1) (1) —. (1) l= , . = , = , E V[. ] 3 45 —4 . (2) (2) (2) l= , . = 0, = 0. E V[. ] 3 So,from Eqs. 27–29, 1 (40+ 108. + 9.2) .7.3, .V[.]= 1 , .V = 644 .E .V[.] . = 2 .4.35, . = .0.034, .V .V — 9 (8+ 24. + 3. 2) .15.9,lE = 4 . .E = 643 (1) 5 (1) 1 (1) 8 (1) —Also . = , . = ,l= —and l= E[2] 8E[11] 2E[2] 5 E[11] 1, from the earlier calculations. Thus, because every type E[11] in Y1, whether remaining intact or not, yields exactly one E[11] for Y (and there are no E[11]-type edges of Y2-genesis because Y2 is side­1 to-side), .E[11]= 2. Therefore .E[2]= .E -.E[11]= 5 27 + .(. + 8) . 15.39. As Fig. 7 suggests, edge 8 64type E[2] now dominates — as re.ected in the 32 epsilon parameters: .2 = 1- (8+ 24. + 3.2)-1 . 9 0.97; .11 = .1 .0.03;.10 = .0 = 0. These calculations are in agreement with the more general treatment of superpositionsgivenin theAppendix. Fig.7. Theboldline-segmentsformtheframe of a 2×1 tiling.Superimposed onitis ourDelaunay tessellation D. Parameters have been chosen so the mean edge lengthsin the two tessellations are equal. ImageAnalStereol2014;33:39-54 A nesting example: Here both Y1 and Y2 are isotropic Poisson line processes, having ‘point processes on line-transects’ with intensities . (1) and .(2) respectively. These point processes are Poisson processes, so the tessellations have the Poisson Transect Property discussed in Remark 1. Also the typical edge in either tessellation has a length that is exponentially distributed. The relevant parameters of Y1 and Y2, calculatedin Miles (1973)are asfollows: (1) . (.(1))2 (1) . (.(1))2 . (1) .V = , .E = , = 4, 42 . (.(2))2 (2) .(2) .V = , .E = (.(2))2 , . (2)= 4, 42 —1 . (1) (1) (1) l= , . = 0, = 0, E . (1) V[. ] (2) 1 (2) . (2) — l= , . = 0, = 0. E . (2) V[. ] From these, and using Eqs. 27–29 together with Lemma3 andEq. 32, we calculate . ((. (1)+ .(2))2 + 2. (1). (2)) , .V = 4 . ((. (1)+ .(2))2 + . (1). (2)) , .E = 2 ..V[. ] .E . (1). (2).V[. ]= , . = and . = 2 . 2 .V .V UsingLemma3,Eq. 32 andEq. 33,we .nd that . 1 . (1)(. (1)+ 2. (2)) = ,lE[Y1]= , .E[Y1] 2 . (1)+ 2.(2) . 1 . (2)(. (1)+ .(2)) = ,lE[Y2]= , .E[Y2] 2 . (1)+ . (2) and .(1)+ . (2) — lE = . (. (1)+ .(2))2 + .(1).(2) Fig. 8shows Y1 and,insidetwo neighbouring cells z and z* of Y1, the nesting by Y2. We note that all edges of Y2-genesis contained in z (or in z*) are of typeE[2]. The .gure also showstheline-segment z.z* which was originally an edge (e say) of Y1. Post­nesting,ithasbeentransformedinto .veedgesof Y1­genesis,butingeneralthe types of these edges maybe E[11], E[10] or E[0] depending on thepositions of the hits of e = z.z* – and whether the hits are caused by chords of z or chords of z*. Fig. 8. The bold lines show the frame Y1 of a line processinto whichindependentcopies of alineprocess Y2 will be nested. In order to focus attention on two neighbouring cells z and z* of Y1 and the .ve post-nesting edges of Y1-genesis on theline-segment z.z*, we only show the nesting in these two cells of Y1. Inside these cells, we see thepost-nestingedges of Y2­genesis as thinlines. Because Y2 has the Poisson Transect Property, Ke has the Poisson distribution with mean 2.(2)l, given the length l of an edge e of Y1. Moreover, given l and given Ke = k > 0, these k hits are uniformly and independently positioned on the edge e and equally likelytobe causedbychordsin z or z*. Thus,the khits create two E[11] edges, an expected (k-1)/2 edges of E[10] type and also an expected (k-1)/2 edges of E[0] type. In Fig. 8, k = 4 and we see two E[0]– edges and one E[10]–edge, along with the two E[11]­type edges. When k = 0, the edge remains type E[2]. Therefore, the typical edge of Y1(in this example all edges of Y1 are type E[2])has an expectednumber of 1. k-1 . PE(1) {Ke = k|l}f(l) dl 0 k.12 type–E[0] edges. Here, f is the probability density function of e’slength l,known tobe .(1) exp(-.(1)l) in this example because Y1 is also a Poisson line process. Evaluatingtheformulaabove,weget 1 . (2. (2)l)k-2. (2)l k-1e-. (1)l .(1) edl . 02 k! k.1 . 1 1(-2. (2)l -1+ 2.(2)l)-. (1)l .(1) = e edl 20 2(. (2))2 = . .(1)(. (1)+ 2. (2)) Anidenticalargumentandresultappliesfor E[10]-type edges. Thereforetheintensities of E[0]-type and E[10]­type edges aregivenby 2(. (2))2 .E[0]= .E[10]= .E (1) . (1)(.(1)+ 2.(2)) ..(1)(. (2))2 = . .(1)+ 2.(2) A similar methodyields 2. (. (1))2.(2) = .E[11] .(1)+ 2.(2) and thisprovides ..(1).(2)(2. (1)+ .(2)).E[1]= .E[11]+ .E[10]= . .(1)+ 2.(2) After tallying both the edges of Y2-genesis and those edgesfrom Y1 whichhavenotbeenhit,wehave .(.(1))3 .E[2]= .E[Y2]+ 2(.(1)+ 2.(2)) .. (. (1))3 .(2)(.(1)+ . (2)) = + . 22(. (1)+ 2. (2)) A check shows that .E[0]+ .E[1]+ .E[2]= .E. Finally one is able to calculate . j = .E[ j]/.E and for the case illustratedin Fig.8,where . (2)= 2.(1),the calculation 8 16 31 yields{.0, .1, .2}= { , , }. 555555 CONCLUSION What have we achieved in this paper that cannot be found in the standard text of Stoyan et al. (1995)? By drawing on the primary sources (Cowan, 1978; 1980; Mecke,1980), the authors ofthis textpresented formulae involving the three intensities .V, .E and .Z and the nine adjacencies µXY where X,Y .{V, E, Z}, one of these adjacencies being equivalent to our . . Stoyan et al. demonstratedthat all of these entities can be expressedasfunctions of .V and . . They also noted — that the metric entities, —aZ,lZ and frame intensity, are functions of the mean edge length l—E (andof .V and . ). Their list of results, which has in.uenced quite a number of studies and other texts, applies to all stationary planar tessellations whether side-to-side or not. The problem is that, when a tessellation is not side-to-side, their results only tell part of the story: just that part which involves the primitive tessellation elements vertices, edges and cells. An interesting and important part of the story, that involving faces of the primitive elements suchas the sides ofpolygonal cells – and the distinction between sides and edges – is not illuminatedby theirlist of results. Ourpaper tells muchmore ofthis story.To explain what is happening with the lower-dimensional faces of edges E and cells Z, we have introduced (via De.nition 4) the four extra object classes E0, S,C and S0 and utilised the extra parameters . , µVE(2), .. and . j, j= 0, 1, 2. Thus we studythe seven classes ofobject {V, E, Z, E0,C, S, S0}compared to the three classes {V, E, Z}studied in Stoyan et al. (1995). We draw upon theincomplete7×7table ofadjacency resultsin WeissandCowan (2011), atable which we complete in Theorem1byemploying thethreeparameters .1, .2 and .3. These three epsilons, although not the only parameters we introduce to describe non side-to-side features, play the central role in our characterisation of tessellations which are not side-to-side.We suggest that they capture the essence of the non side-to-side structure. Many examples, some interesting in their own right and others mainly for reinforcement of the ideas, round out the theories. ACKNOWLEDGEMENT We thank the reviewersfor their careful reading of the manuscript andfor their suggestions. After this paper was submitted for publication, a third editionofthetextby Stoyanetal appeared(see Chiu et al. (2013)). Thatedition embraces many ofthe ideasandnotationsof WeissandCowan (2011). The text now makes use of the parameter . from Cowan (1978), and presents a distinction between sides and edges.Nevertheless,ourpaperdeals with theseissues in muchgreaterdetail, through ourintroduction of the parameters.1, .2 and .3. REFERENCES Chui SN, Stoyan D, Kendall WS, Mecke J (2013). StochasticGeometry anditsApplications. 3rd Ed. Chichester:Wiley. CowanR(1978).The useof ergodictheoremsinrandom geometry.SupplAdvApplProb10:47–57. Cowan R (1979). Homogeneous line-segment processes. MathProcCambPhilSoc86:481–9. Cowan R (1980). Properties of ergodic random mosaic processes.MathNachr97:89–102. CowanR,MorrisVB(1988).Division rulesforpolygonal cells.JTheorBiol 131:33–42. Cowan R (2004). A mosaic of triangular cells formed with sequential splitting rules. J Appl Prob Spc Vol 41A:3–15. Cowan R (2010). New classes of random tessellations arising from iterative division of cells. Adv Appl Prob 42:26–47. ImageAnalStereol2014;33:39-54 CowanR(2013).Line-segmentsintheisotropicplanarSTIT tessellation.AdvApplProb 45:295–311. CowanR,TsangAKL(1994).Thefalling-leaf mosaic and its equilibriumproperties.AdvApplProb 26:54–62. Gr¨unbaumB,ShephardGC(1987). Tilings andPatterns. NewYork: WHFreeman. Heinrich L, Muche L (2008). Second-order properties of the point process of nodes in a stationary Voronoi tessellation.MathNachr 281:350–75. Leistritz L, Z¨ahle M (1992). Topological mean value relationships for random cell complexes. Math Nachr 155:57–72. MaierR,SchmidtV(2003).Stationaryiteratedtessellations. AdvApplProb35:337–53. Mecke J (1980). Palm methods for stationary random mosaics. In: Ambartzumian RA, Ed. Combinatorial Principles in Stochastic Geometry. Erevan: Armenian Academy ofScience. MeckeJ(1984).Parametric representation of mean values for stationary random mosaics.MathOperationsStatist SerStatist15:437–42. Mecke J, Nagel W, Weiss V (2007). Length distributions of edges in planar stationary and isotropic STIT tessellations. Izvest Akad Nauk Armen Matem 42:39– stable tessellations.AnnProb 41:2261–78. Stoyan D, Kendall WS, Mecke J (1995). Stochastic Geometry and its Applications. 2nd Ed. Chichester: Wiley. . l Weiss V, Cowan R (2011). Topological relationships in spatial tessellations.AdvApplProb 43:963–84. Weiss V, Z¨ ahleM(1988).Geometric measuresfor random curved mosiacs of Rd.MathNachr 138:313–26. APPENDIX: SUPERPOSITION AND NESTING FORMULAE This Appendix links our formulae, Eqs. 6–8, with superposition and nesting. It supplements the section where these two tessellation operations and related terminology arede.ned, and shouldbe readinparallel withit. Assuming that Y2 is isotropic, we ask what is the expected number of Y2-genesis edges in Y contained in the typical cell of the Y1 tessellation? To answer this question, we simply condition on the area and perimeter of a Y1-genesis cell z, apply (2)(2) — and . Eq. 6 (with W = z and using for the E E l — E and .E in this formula) and take the expectation 60. l l EZ(1) of the conditioned entities. This gives (in both Mecke J, Nagel W, Weiss V (2011). Some distributions the superposition and nesting contexts) an expected for I-segments of planar random homogeneous STIT number of edges of Y2-genesis contained in a typical tessellations.MathNachr 284:1483–95. cell of tessellation Y1 as MilesRE(1970).OnthehomogeneousplanarPoissonpoint — E — (2) ( process.MathBiosci6:85–127. EZ(1)(Kz(E(2))) = Miles RE (1973). The various aggregates of random ) (1)(1)(2) + a—Z .E (30) . Z . polygons determined by random lines in a plane. Adv Using Eq. 30, the intensity of edges of Y2­ Math 10:256–90. (1) (2) (1)(1)(2) l — Z genesis is . Z /. + a— ) . E which equals MollerJ(1989).RandomtessellationsinRd.AdvApplProb l ( — E Z (2) (1) (2)(1) l — E l — E 21:37–73. . . /.) from Eq. 2and Eq. 4. (1+ 2 E E NagelW,WeissV(2003).Limits ofsequences of stationary planar tessellations.AdvApplProb35:123–38. Nagel W, Weiss V (2005). Crack STIT tessellations: characterization of stationary random tessellations stable with respect to iteration. Adv Appl Prob 37:859–83. Santal´o LA (1984). Mixed random mosaics. Math Nachr 117:129–33. Schneider Stochastic anSpringer. R, Weil d Integral Geometry . W Berlin Heidelberg: (2008). Schreiber T, Th¨C (2010). Second-order properties ale and central limit theory for the vertex process of iteration in.nitely divisible and iteration stable random tessellationsin theplane.AdvApplProb 42:913–35. l l REMARK 7: In Eq. 30, we use EZ(1)( · ) to indicate that the ‘typicality expectation’ is taken for cells z . Z(1), that is, only cells of Y1. We have used E(2) for the argument of Kz to indicate that we count only the edges of Y2. In this Appendix, however, edges are the only objects of Y2 that we count – we don’t count other entities such as vertices or cells – and so, for brevity, we drop entirely the bracketed argument of K that was a necessary part of Eqs. 6–8. We retain only the subscript argument, so theleft–handpart ofEq. 30 simpli.es to EZ(1) Kz. Using Eq. 8 similarly, the expected number of edges of Y2-genesishitting the typical type–X edge of Y1 is 2 (1)(2)(2) —— . (31) EX(1) Kx = X E E Schreiber T, Th¨ aleC(2013). Limit theoremsforiteration 53 . for the superposition and double this value for the nested tessellation due toindependent hits of the edge from both adjacent cells (see Fig. 8 for illustration). Here x .X. In the superposition case, all of these hits create .- -vertices(of order4) on this edge of Y1;in the nesting case, all thehits are . -vertices(of order3). Therefore the intensity of Y1-genesis edges in Y is . (1)(1 + EE(1) Ke) which can be evaluated E E(1) from Eq. 31 using X = . The overall edge intensity in Y is that given in Eq. 27, in agreement withformulae(4.6) and(4.17) of Maierand Schmidt (2003). Moreover, accounting for the new vertices created whoseintensityisgivenby Eq. 31, the overall intensity .V of vertices is as per Eq. 28, in agreement withformulae(4.5) and(4.16) ofMaierandSchmidt. Thus we have proved the following result, presentedhereasa Lemma. LEMMA 3: Let E[Y j] denote the class of Y j­genesisedges. Theintensity of edgesof Y2-genesisis ( ) 2 .E[Y2] E (2) (1)(2)(1) —— = . 1+ ll . , EEE . both for superpositions and nestings. The intensity of edges of Y1-genesis equals .E -.E[Y2], or .() (1) 2 (1)(2)(2) . —— . . 1+ ll . , (S) E . EEE = .E[Y1] ( ) . (1) 4 (1)(2)(2) . l—l—. , (N). .E 1+ EEE . The proportion of edges which are of Y j-genesis equals .E[Y j]/.E. Moreover, in both contexts, the frame intensity of Y equals the sum of frame intensities for Y1 and Y2. (1)(1)(2)(2) ——— This means that lE.E = l . + l . ; so the EE EE mean edgelength of Y is asfollows: (1)(1)(2)(2) — l . + l—. EE EE — lE = . (32) .E Itis alsotruethatlE[Y j].E[Y j] equalsthe frameintensity ( j)( j) of Y j, asdoes l—. . So EE ( j)( j) — lE .E lE[Y j]= , j= 1, 2. (33) .E[Y j] Furtherformulae, relevant to our study andproved with similar accountancy, aregiveninthe main section on superposition and nesting. The tessellation Y2 need not be isotropic for these formulae above to hold. If it is Y1 that is isotropic and Y2 not, then the formulae still hold (though the argument is more elaborate and works because the typical cell and typical edge of Y1 would then be isotropic random sets). COWAN R ET AL: Non side-to-side tessellations Edge-types formed with superposition: With superpositions, the number of hits by the edges of Y2 on a typical edge x in Y1 of type X is denoted by Kx. It has expectation given in Eq. 31. The Kx hits partition the original type–X edge into Kx + 1 edges. When X = E[11], one of the created edges is E[11] and the remainder are E[2].When X = E[2], all of the created edges are of type E[2]. The situations when X = E[10] or X = E[0] edges are more complicated, because the Kx + 1 resulting edges comprise two of type E[11] and (Kx -1) of type E[2] when Kx > 0. When Kx = 0, the edge type is unchanged. So, the intensities of edges in Y are givenbelow, where thee in termslikeP· ](1) {Ke = 0} E[ or EE[ · ](1) Ke refers generically to an edge in E[ · ](1) (the subscriptofthePalm measure orPalm expectation applying to that term). (1) = . P .E[10] E[10] E[10](1) {Ke = 0}, (1) .E[0]= .E[0] PE[0](1) {Ke = 0}, (1)(1) .E[11]= .E[11]+ 2.E[10] PE[10](1) {Ke > 0} (1) + 2. PE[0](1) {Ke > 0}, E[0] and () (2) 2 (1)(2)(2) —— = . 1+ ll . .E[2] E . EEE () (1)(1) + . 1+ EE[2](1) Ke+ . E E[2]E[11]E[11](1) Ke () (1) + .E[10]EE[10](1) Ke -PE[10](1) {Ke > 0} () (1) + . EE[0](1) Ke -PE[0](1) {Ke > 0}. E[0] The .rst term of the .E[2] expression accounts for Y2­genesis edges andthe otherthreeterms accountforY1­genesis edges. Expressions above involving PX(1) {Kx > 0}or PX(1) {Kx = 0}can be evaluated in some models, notably those which have the ‘Poisson Transect’ property(seeRemark1). These expressions are also easy to evaluateif Y1 has no edges of types E[10] and E[0] (see the calculationfor the2×1–tiling). Edge-types formed by nesting: With nested tessellations, the theory for edges of Y2-genesis has beendealtwithin Lemma3. The number ofhitsby the edges of Y2 on a typical edge x in Y1 of type X is denoted, as before, by Kx. It now has expectation given by double the value in Eq. 31. The Kx hitspartitionthe original type–X edge into Kx + 1 edges, but an analysis of the types of edge(E[2], E[11], E[10] or E[0])is dif.cult, except in cases where Y2 is a tessellation whichhas the Poisson Transect propertythatwementionedinRemark1. The penultimate sectiongives suchan example.