Image Anal Stereol 2018;37:83-98 doi:10.5566/ias.1621
Original Research Paper
LINE SEGMENTS WHICH ARE UNIONS OF TESSELLATION EDGES
RICHARD COWANB,1 AND VIOLA WEISS2
1School of Mathematics and Statistics, University of Sydney, NSW 2006, Australia.; 2 Ernst-Abbe-Hochschule,
Jena, Germany.
e-mail: richard.cowan@sydney.edu.au, viola.weiss@eah-jena.de
(Received September 8, 2016; revised January 19, 2018; accepted January 29, 2018)
ABSTRACT
Planar tessellation structures occur in material science, geology (in rock formations), physics (of foams, for
example), biology (especially in epithelial studies) and in other sciences. Their mathematical and statistical
study has many aspects to consider. In this paper, line-segments which are either a tessellation edge or a finite
union of edges are studied. Our focus is on a sub-class of such line-segments – those we call M-segments
– that are not contained in a longer union of edges. These encompass the so-called I-segments that have
arisen in many recent tessellation models. We study the expected numbers of edges and cell-sides contained
in these M-segments, and the prevalence of these entities. Many examples and figures, including some based
on tessellation nesting and superposition, illustrate the theory. M-segments are much more prevalent when a
tessellation is not side-to-side, so our paper has theoretical connections with the recent IAS paper by Cowan
and Thäle (2014); that paper characterised non side-to-side tessellations.
Keywords: combinatorial topology, edge types, planar tessellations, STIT tessellation, stochastic geometry,
superposition/nesting.
INTRODUCTION
In this paper we study geometric structures seen
in random planar tessellations: namely line-segments
which are either a tessellation edge or a finite
union of edges. Collectively, we call these structures
tessellation segments (see Definition 1). Of course, to
achieve a finite union which is a line-segment, the
edges contributing to the union must be collinear.
Some of these tessellation segments are maximal
in the sense of Definition 1.
Definition 1. A closed and bounded line-segment
which is either an edge of the planar tessellation
or a finite union of the tessellation’s edges is called
a tessellation segment. An M-segment is a maximal
tessellation segment. It is ‘maximal’ in the sense that it
is not contained in a longer tessellation segment.
It is the class of M-segments that attracts our main
attention in this paper, though we also look at a sub-
class, the I-segments – which have been discussed in
earlier studies.
Definition 2. A vertex of the tessellation is called a
π-vertex if and only if the edges emanating from the
vertex subtend one angle of π . An I-segment is an M-
segment with π-vertices at both ends. So I⊆M.
An M-segment may have non-π vertices (written
π̄-vertices) at its two end points (termini); only if both
of these termini are π-vertices does the line-segment
(together with a small neighbourhood of its termini)
look like the letter I, hence the name I-segment. Fig. 1
shows examples of π-vertices, I-segments and M-
segments.
The role of π-vertices was first discussed in Cowan
(1978; 1980). The name I-segment was first used in
papers by Mackisack and Miles (1996) and Miles and
Mackisack (2002) dealing with particular models for
planar tessellations.
π
π
Fig. 1. The bold black line-segment is an M-segment
that is not an I-segment. The two white segments, one
comprising two edges and the other only one, are I-
segments. Two of the many π-vertices in the figure
have their subtended π angle marked. The white disk
is discussed in Remark 2.
83
COWAN R ET AL: Unions of tessellation edges
I-segments were also analysed in the context of
the so-called STIT model by Mecke et al. (2007;
2011) and Cowan (2013). In this model and those of
Miles and Mackisack, all vertices are π-vertices. Some
other models, for example the Gilbert model (Gilbert,
1967) and various iteratively-divided models in Cowan
(2010) also have this feature. So there were no M-
segments that were not I-segments in these earlier
studies. In other words, M\I= /0 for the models whose
I-segments have to date been discussed.
Our current study is model-free; we only impose
stationarity of the planar tessellation (an invariance
of the tessellation’s statistical properties under
translation) and convexity of its cells – so they are
convex polygons – together with a local-finiteness
condition (any bounded domain intersects a finite
number of cells). Furthermore we assume that both
the vertex intensity (the mean number of vertices per
unit area) and the mean length of the typical edge
are positive and finite. In this general context, which
embraces all stationary planar tessellations except
those where no M-segments exist, we derive formulae
for the composition of the typical M-segment: the
expected number of edges and the expected number of
cell-sides lying in the M-segment. Also we find these
results for superposition and nesting of tessellations.
With no further assumptions about the tessellation
structure, one cannot obtain distributional results, but
these mean-value results are of interest and new.
BASIC TERMINOLOGY AND
NOTATION
Our discussion adopts the language and concepts
of the earlier papers, Weiss and Cowan (2011) and
Cowan and Thäle (2014). A tessellation of the plane
is a collection of compact convex polygonal cells
which cover the plane and overlap only on cell
boundaries. The union of the cell boundaries is called
the tessellation frame. Each cell has sides and corners,
these being respectively the 1-faces and 0-faces of the
polygon; they lie on the frame. The union (taken over
all cells) of cell corners is a collection of points in
the plane called the vertices of the tessellation. Those
line segments which are contained in the frame, have a
vertex at each end and no vertices in their interior1 are
called edges of the tessellation.
Remark 1. It is useful here, now that the concept of a
cell side has been introduced, to note that a π-vertex is
a vertex which lies in the interior of a cell side. Clearly,
π̄-vertices do not.
As discussed in Weiss and Cowan (2011), the focus
of attention in many studies of planar tessellations and
tilings has been the side-to-side case.
Definition 3. A tessellation is side-to-side if, for every
cell, each side of that cell coincides with the side
of another cell. Equivalently, one can say that a
tessellation is side-to-side if and only if it has no π-
vertices.2
In the non side-to-side case, the distinction between
edges and sides is important. We note that some writers
use the term edge-to-edge where we say side-to-side;
we see no logic in the edge-to-edge terminology once
the distinction between edges and sides is recognised.
Primitive and non-primitive elements: The
tessellation’s primitive geometric elements, treated as
compact domains, are the vertices, edges and cells.
The collections of these elements are denoted by V,
E and Z (for Zellen) respectively (and we note that
V,E and Z are sets, because no element appears more
than once). Other compact geometric elements will
be introduced and the collection of these will also
be denoted by a non-sloping upper-case letter – for
example, S and C for all sides and corners of cells,
respectively. As seen above, M and I are the sets of
M-segments and I-segments respectively. Tessellation
frames may contain infinite-length full lines and the
set of these full3 lines is called L.
We note that, for those elements which are not
primitive but are instead derived from a primitive
element or from some other feature of the tessellation,
then the collection might have elements which appear
more than once. We call these collections multisets.
For example, there will be many corners located at
each vertex; thus we speak of the multiset C of corners.
Likewise, we have a multiset S of sides. In side-
to-side tessellations, every element in S equals another
member of S, as befits the terminology side-to-side.
This may be true for some (but not all) members of S
in the non side-to-side case. In general, cell sides are
1Here the interior of a line-segment, or indeed of any object x of lower dimension than the space of the tessellation, is defined using
the relative topology on x. So when we use the word ‘interior’ in such contexts, we mean ‘relative interior’.
2 A side-to-side tessellation is obviously corner-to-corner in the sense that, for every cell, each corner of that cell is the corner of
another cell. These concepts are encompassed in the d-dimensional discussion of Schneider and Weil (2008), page 447, where the general
phrase face-to-face is used – see also Lemma 1.1 of Cowan and Weiss (2015).
3 Full lines extend infinitely in both directions. Later we discuss half-lines, which extend infinitely in only one direction – showing (via
Lemma 3) that these don’t exist in stationary tessellations. At this stage, we merely say that L does not includes half-lines and, from now,
the word ‘line’ means ‘full line’.
84
Image Anal Stereol 2018;37:83-98
line-segments which equal an edge or a finite union
of edges. So S, like M and I, only contains elements
which are tessellation segments.
Generic (multi)sets of geometric objects are
denoted by X and Y. Sub(multi)sets of X are denoted
by X[·], with the contents of the [·] being a suitably
suggestive symbol introduced in an ad hoc manner. For
example, we denote the subset of π-vertices by V[π],
the subset of non π-vertices (π̄-vertices) by V[π̄ ], the
‘sub-multiset’ of corners which lie on π-vertices by
C[π] and the subset of vertices which lie on exactly
j lines ∈ L by V[L, j].
Remark 2. From any multiset, a reduced set of
elements ignoring all multiplicities can be constructed
– also a function mapping this reduced set into
the positive integers can indicate the multiplicities.
Thus a multiset might be called a marked set, the
‘mark’ indicating the multiplicity of an element. With
this device, calculations can proceed quite logically,
though it would be notationally complicated if spelt
out completely with algebraic symbols for reduced
sets and mark functions. We avoid such detail as
our calculations with multisets are intuitively clear.
For example, if we asked for the number of sides
intersecting the white disk in Fig. 1, we expect our
reader to answer: 16. For corners: 8, counting the
multiplicities in C at three vertices.
In the early part of the twentieth century, when
the axioms of mathematics were being established
in terms of sets and functions (see Kline (1980)),
the simplifying decision to use sets, rather than
the more general multisets, led to a neglect of the
latter. A century later, it is now recognised that
multisets are merely a notational complication to
the ‘Zermelo/Fraenkel/Axiom-of-Choice’ framework,
not an illegitimacy. In describing the history, Blizard
(1989) shows many situations in mathematics where
multisets occur naturally.
Intensities: Under our assumption that the
tessellation is stationary, the centroids of all members
in a (multi)set of bounded objects form a stationary
point process on the plane, but this process might
also have point multiplicity and, if so, it would not
be a simple point process. Nevertheless we can always
define a point-process intensity.
Definition 4. The intensity of objects belonging to
class X of bounded objects is the expected number of
centroids, of the elements of X, in any domain of unit
area. It is denoted by λX.
Note that, because lines are unbounded objects
without centroids, we do not define λL – and likewise
for any other class containing unbounded objects.
One of the intensities is needed as a scale
parameter – and we have chosen λV to play this role.
We assume that
0 < λV < ∞ . (1)
Introducing parameters φ and θ : We now define
two important parameters that quantify vertex features.
Definition 5. We denote the ‘proportion of vertices
that are π-vertices’ by the parameter φ . Equivalently,
φ is the probability that the typical vertex is a π-vertex.
Another fundamental parameter of the random
tessellation is θ .
Definition 6. The number of edges emanating from a
vertex is called the valency of that vertex. The average
valency of the typical vertex is denoted by θ .
In an earlier study (Weiss and Cowan, 2011), we
proved the following constraints,
0 ≤ φ ≤ 1 and 3 ≤ θ ≤ 6−2φ , (2)
and showed that the other main intensities are
expressed as follows in terms of λV,θ and φ :
λE=
θ
2
λV , λZ =
θ −2
2
λV , λS=λC =(θ −φ)λV .
(3)
We also showed that the expected number of edges
contained in the typical cell-side, is θ/(θ −φ).
A metric parameter: There are many metric
entities in a tessellation, for example, lengths of
various line-segments, perimeters of cells and areas
of cells. For this paper, we need to introduce just one
basic metric parameter: ℓ̄E, the expected length of the
typical tessellation edge. The symbol ℓ̄X is introduced
to be the expected length of the typical line-segment
from some class X of line-segments, but if we find a
value of ℓ̄X for examples of X, it will be in terms of ℓ̄E.
We assume that
0 < ℓ̄E < ∞. (4)
So Eqs. 1 and 4 are the two first-moment assumptions
that we anticipated at the end of our Introduction.
Remark 3. Clearly, all of the intensities, λE,λZ,λS
and λC given in Eq. 3, are positive and finite. This
follows from the finite bounds on θ and φ given by
Eq. 2 together with the identities in Eq. 3 and our
assumption Eq. 1 that 0 < λV < ∞. Similarly, our
assumption Eq. 4 combined with Eq. 2 shows that
all the expected lengths ℓ̄X (that are proportional to
ℓ̄E, with the proportionality constant a function of θ
and/or φ ) are finite and positive. For example, it is
shown in Cowan and Thäle (2014) that, when X = S,
ℓ̄S = θ ℓ̄E/(θ −φ), so clearly ℓ̄S is finite and positive.
85
COWAN R ET AL: Unions of tessellation edges
The concept of ‘adjacency’: This concept, which
has a unifying role in tessellation theory, is defined as
follows.
Definition 7. An object x ∈ X is said to be adjacent
to an object y ∈ Y if either x ⊆ y or y ⊆ 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
define µXY as the expected value of mY(x) when x is
the typical member of X. In this notation, we envisage
the centroid of the member in X as our ‘position of
viewing the tessellation’, and the objects in Y as those
that we count.
Formally, we write µXY := EX(mY(x)) =
∫
mY(x)PX(dx), where EX denotes an expectation for
the typical object of type X (that is, defined with respect
to the Palm measure PX; see Chiu et al. (2013)).
If B(r) is the ball of radius r centred at the origin,
µXY can also be defined formally as
lim
r→∞
∑{x∈X: centroid of x is ∈ B(r)} mY(x)
number of x ∈ X with centroid ∈ B(r) , (5)
when the limit shown is a constant; see Cowan (1978;
1980).
We can now present an alternative definition of φ
using the adjacency concept and Remark 1.
Remark 4. A vertex is a π-vertex if and only if it is
adjacent to the interior of a cell-side. In this context,
being ‘adjacent to’ is equivalent to being ‘contained
in’. Thus we can write φ using the adjacency notation.
φ := µ ◦VS , (6)
the expected number of ‘side-interiors’ adjacent to a
typical vertex.
Note that
◦
X denotes the class comprising the
interiors of objects in class X; also λ ◦
X
:= λX. Thus
◦
S
in Eq. 6 denotes the (multi)set of all side-interiors.
Remark 5. The other fundamental parameter, θ , can
also be expressed using the adjacency notation. In
words, θ equals the expected number of edges adjacent
to the typical vertex. In symbols, θ ≡ µVE .
Exchange formulae: We have a historical
attachment to the symbol θ , due to its extensive use in
our earlier papers. Whilst we have continued its use in
this paper, we prefer to use µVE in the calculations that
follow, because the letter-subscripts give reminders of
which two object classes are involved in the adjacency
count. As calculations often switch focus on the object
type which is our position of viewing, the use of µVE
instead of θ can be helpful. For example, an important
tool is the following identity, known as ‘an exchange
formula’. When X and Y are both primitive-element
sets,
λXµXY = λYµYX . (7)
This identity also holds more generally (Weiss and
Cowan, 2011). Notice that the identity involves two
different positions of viewing, one from a typical X
object the other from a typical Y object. As a trivial
example, let X = E and Y = V. Aided by the obvious
identity µEV = 2, Eq. 7 yields the usual proof of the
first part of Eq. 3: λE = λVµVE/µEV =
1
2
θ λV. As a
more elaborate exercise, we now prove that λS, the
intensity of sides, is as shown in Eq. 3. We note that
µSE−µ ◦SV = 1. Therefore
λS = λSµSE−λSµ ◦SV
= λEµES−λVµ ◦VS
= 2λE−φλV
= (µVE−φ)λV , (8)
using identities Eqs. 7 and 6 together with the obvious
identity µES = 2 (each edge being adjacent to two
sides).
TWO LEMMAS: The most important new intensity
established in this paper is that of the M-segments. We
shall prove the following lemma in later sections.
Lemma 1. The intensity of the point process formed
by the centre-points of the M-segments is
λM =
1
2
(µVE−2µ ◦VM−2µVL)λV .
A second lemma, though deceptively obvious4, is
also useful.
4 A statistician, considering the sampling of a random vertex in D, might, for example, question why φ is a ratio of expectations in
result (a) of Lemma 2, rather than the conditional expectation of a ratio,
number of π-vertices ∈ D
number of vertices ∈ D
given that the ratio’s denominator is > 0? He/she might also insist that D should be a very large domain. There are some deep issues here
concerning the motivational link between Palm probability measures and ergodic theory. Indeed, if one takes this statistical view and starts
with this conditional expectation and a large D tending to cover the whole plane, one can prove (a).
86
Image Anal Stereol 2018;37:83-98
Lemma 2.
(a) φ =
λV[π]
λV
and (b) φ = µVV[π].
The former is the ratio of the expected number of π-
vertices in any domain D to the expected number of
vertices in D. The latter, which involves a class of
points and one of its sub-classes, is a general way to
write the probability that a typical member of the class
is a member of the sub-class.
Proof of Lemma 2: (a) Using Eqs. 7 and 6, λV φ =
λV µ
◦
VS
= λ ◦
S
µ ◦
SV
. But µ ◦
SV
= µ ◦
SV[π] and therefore
λ ◦
S
µ ◦
SV
= λ ◦
S
µ ◦
SV[π] = λV[π] µ
V[π]
◦
S
. Because µ ◦
V[π]S = 1,
we have proved that λV φ = λV[π]. Thus part (a) is
proven.
(b) Once again we use Eq. 7. λVµVV[π] =
λV[π]µV[π]V. Note that µV[π]V = 1. Thus, using part (a),
the proof of part (b) is complete. 
THE MAIN ADJACENCY RESULTS
OF THIS PAPER
Our central results on M-segments, proved later,
can be expressed as adjacencies. Via the following
theorem we find formulae for µME and µMS,
respectively the expected number of edges and cell-
sides adjacent to the typical M-segment (in other
words, contained in the typical M-segment).
Theorem 1. For all our stationary planar
tessellations,
µME =1+
2 µ ◦
VM
µVE−2(µ ◦VM+µVL)
, and (9)
µMS =





2 µME , φ = 0 ,
2
(
1+
2 µ ◦
VM
−φ µ ◦
V[π]M
µVE−2(µ ◦VM+µVL)
)
, φ > 0 .
(10)
We note that µ ◦
V[π]M is undefined when φ = 0 (as
then there are no π-vertices), hence the two cases
within Eq. 10.
Most of the adjacencies on the right-hand side of
these identities have the typical vertex as the ‘point
of viewing’. For µVL and µ
◦
VM
we need to count the
expected numbers of lines and M-segment-interiors
adjacent to the typical vertex and µVE, the expected
valency of the typical vertex. The typical π-vertex, is
also involved when the tessellation is not side-to-side,
that is, when φ > 0.
EXAMPLES
Before proving Theorem 1 and Lemma 1 in
the later sections, we present some examples which
build experience of these tessellation entities and the
formulae given above.
Fig. 2. The planar tessellation formed as the
superposition of a Poisson-Voronoi tessellation and its
Poisson-Delaunay ‘dual’. See Example 1 for further
definition.
Example 1. Superposition of a Poisson-Voronoi
tessellation and its Delaunay dual: Superposition
of two tessellations is a commonly used operation
in tessellation theory. The operation is defined by
saying that its frame is the union of the frames of
the component tessellations. In this example illustrated
by Fig. 2, the two tessellations are highly dependent,
being the Voronoi and Delaunay tessellations based
on the same set of seeds. The seeds are positioned
according to a Poisson point process of intensity ρ .
The figure has been taken from Weiss and Cowan
(2011), where it is shown that the vertex intensities
of the Delaunay and Voronoi components are ρ and
2ρ respectively. Furthermore the intensity of vertices
which result from frame-crossings is 4ρ (a fact from
Muche (2005)).
In Example 1 there are no lines, so µVL = 0. Also
there are no π-vertices, so φ = 0, µ ◦
V[π]M is undefined
and µMS = 2µME.
The mean vertex valency in a Delaunay tessellation
is 6; in a Voronoi, vertices have valency 3 with
probability 1. All vertices that are frame-crossings
have valency 4. So µVE =
2
7
· 3 + 1
7
· 6 + 4
7
· 4 = 4.
Finally, µ ◦
VM
= 4
7
· 2 = 8
7
because only frame-crossing
vertices have adjacent M-segment-interiors (and 2 of
them). Therefore, µME = 1+
16
7
/(4− 16
7
) = 7
3
. (Note
that, treated individually, the Voronoi and Delaunay
tessellations have µ ◦
VM
= 0 and hence µME = 1 and
µMS = 2). 
87
COWAN R ET AL: Unions of tessellation edges
Fig. 3. A Voronoi tessellation with each cell split by a
random chord through the seed used to generate that
cell. These seeds are not shown; the original Voronoi
vertices are shown with dots. See Example 2.
Example 2. Poisson-Voronoi cells each divided by
a chord: The cells in a Poisson-Voronoi tessellation,
whose seeds are a Poisson point process of intensity ρ ,
are each divided by a random chord through the cell’s
seed (in such a way that the chord creates two new π-
vertices). See Fig. 3.
The original Voronoi vertices have intensity 2ρ ,
as do the new vertices (because each chord generates
two new vertices). These new vertices are π-vertices,
so φ = 1
2
and µ ◦
V[π]M = 1. Also each new vertex is
adjacent to one M-segment-interior while each old
vertex is not adjacent to any M-segment-interior, so
µ ◦
VM
= 1
2
. There are no lines, so L is null and µVL = 0.
With probability one, all vertices have valency 3, so
µVE = 3. Therefore µME = 1 + 1/(3 − 1) = 32 and
µMS = 2(1+(1− 12 ·1)/(3−1)) = 52 . 
Fig. 4. A model based on the triangular lattice. See
Example 3.
Example 3. A tessellation based on a triangular
lattice: Consider the regular lattice of equilateral
triangles as a tessellation, made random and
stationary by randomly locating the origin of R2
uniformly distributed in one of the triangles. For
each cell independently, draw a chord by randomly
choosing two sides of the triangle and joining the mid-
points of those chosen sides (see Fig. 4).
Without loss of generality, suppose that the
original triangles that form the lattice have area 1.
Each original triangle has three corners; counting all
of these and saying that the vertex intensity of the
lattice-tessellation is ‘3 per unit area’ is obviously a
six-fold error (as each vertex would be counted six
times). Adjusting for this, we see that the mean number
of lattice tessellation vertices per unit area is 1
2
and
each such vertex has valency 6. It is also adjacent to
three lines and to zero M-segments.
A similar argument shows that the intensity of mid-
points of the lattice triangles’ sides is 3
2
per unit area.
Such a mid-point has
– a probability 1
9
of not being a vertex of the final
tessellation (because this is the chance of it not
being a terminus of any random chord),
– a probability 4
9
of being a π-vertex of valency 3
in the final tessellation (being the terminus of one
random chord), adjacent to one line and zero M-
segments,
– a probability 4
9
of being a π̄-vertex of valency 4
in the final tessellation (being the terminus of two
random chords), adjacent to one line and having an
expected adjacency 1
2
to an M-segment-interior.
So 3
11
of vertices in the final tessellation are adjacent
to 3 lines and 8
11
are adjacent to one line; therefore
µVL =
17
11
. Likewise 2
11
of vertices lie in the interior of
one M-segment, the remaining vertices zero. Therefore
µ ◦
VM
= 2
11
. Regarding π-vertices, φ = 4
11
and µ ◦
V[π]M =
0.
We need µVE for our formulae. From the
information above, λV =
1
2
+ 3
2
( 4
9
+ 4
9
) = 11
6
and µVE =
3
11
·6+ 4
11
(3+4) = 46
11
.
Since each of the original triangles is divided into
two cells, there are two cell-centroids per unit area
in the final tessellation. So λZ = 2 and, from Eq. 3,
λV = 2/(µVE−2)λZ = 4/( 4611 −2) = 116 . This provides
a check on the earlier calculation of λV.
We can now find µME and µMS.
µME = 1+
2 · 2
11
46
11
−2( 2
11
+ 17
11
)
=
3
2
,
µMS = 2 µME ,
because µ ◦
V[π]M = 0. This is consistent with another
simple calculation (available in this example, but not
generally) which shows that the number of edges in
a typical M-segment is distributed geometrically on
{1,2, ...} with mean 3
2
. 
88
Image Anal Stereol 2018;37:83-98
Fig. 5. Topology like the STIT tessellation. See
Example 4.
Example 4. The STIT tessellation and others similar.
The STIT model, which plays a central role in
tessellation theory, has no lines and all vertices are
π-vertices of valency 3. So all M-segments are I-
segments; see Fig. 5. Some other models, for example
the Gilbert model (Gilbert, 1967), the Arak-style model
studied by Miles and Mackisack (2002) and many of
the iteratively-divided models in Cowan (2010) (of
which STIT is an important example), also have these
features.
So φ = 1 and µVE = 3 for this class of tessellations.
Also µ ◦
V[π]M = 1 and µVL = 0 because the class L is
empty. Therefore, for all these no-lines models where
all vertices are π-vertices of valency 3, µME = 1 +
2/(3− 2) = 3 and µMS = 2(1+(2− 1)/(3− 2)) = 4.

Fig. 6. The tessellation frame of Example 5 is shown in
black. A black dot at a vertex indicates that this vertex
is a π-vertex. The square lattice prior to the migration
of vertices is shown in white.
Example 5. Migrating vertices: The construction of
this example begins with the standard lattice of unit-
side squares, made into a stationary tessellation by the
usual device of placing the origin uniformly distributed
inside one of the squares. Then independently for
each vertex of the tessellation a random movement
is created, moving a vertex v originally at (x,y) to
(x ± 1
4
,y ± 1
4
). The four possible new positions each
have probability 1
4
. See Fig. 6. Note that every vertex
has valency four, so our new tessellation has µVE = 4.
Also we have no infinite lines, so L= /0 and µVL = 0.
We focus on the case v = (x,y), seen in the centre
of Fig. 7, moving north-east (NE) to (x+ 1
4
,y+ 1
4
). The
figure also displays the four ‘neighbouring’ vertices
(those connected to v by an edge).
Fig. 7. As indicated by the arrows, there are four
possible movements at each ‘neighbour’ of our vertex
v, which we assume moves NE from its initial position
(x,y).
Fig. 7 demonstrates that there are 44 (or 256)
different changes to the positions of v’s neighbours.
Fig. 8. The North and East neighbours have been
given a SW movement ւ. This is the only way that
the central vertex v can become, post-migration, a π-
vertex. The remaining two neighbours still have 42
different changes of position. Thus the probability that
the arbitrary vertex v is a π-vertex is 42/44.
89
COWAN R ET AL: Unions of tessellation edges
Fig. 8 shows that the post-migration φ = 16
256
= 1
16
.
Note that a π-vertex is created in Fig. 8 at the vertex
v because it and the two vertices given a ւ movement
are collinear. This fact is emphasised by our dashed
line-segment in Fig. 8. In this figure, we also note that
v lies in the interior of exactly one M-segment interior.
Thus µ
V[π]
◦
M
= 1.
For the calculation of the only remaining input to
Theorem 1, namely µ
V
◦
M
, we present one more arrow
diagram: Fig. 9. It leads to the table below – which
gives the number n j of changes of position whereby v
lies in the interior of j M-segments.
j 0 1 2
n j 128 112 16
Showing that n2 = 16: Fig. 9 shows the only
cases where our vertex v lies in the interior of two
M-segment interiors, of which the two dashed line-
segmentss are part. Note that, to achieve this, the East
and West neighbouring vertices are each permitted
only two movements, տ and ր, whilst the other two
(the North and South neighbours of v) are permitted
only ց and ր. Thus there are 24 (or 16) different
changes of position allowed.
Fig. 9. The two dashed line-segments each contain the
migrated position of the central vertex v.
Showing that n1 = 112 and n0 = 128: The
horizontal line-segment in Fig. 9 occurs only when
both the East and West neighbours of v have arrows
տր, implying 22 possible movements for these
two neighbours. But, in total, there are 42 possible
movements for them. Thus there are 42 − 22 = 12
possible movements for the East and West neighbours
where the horizontal dashed line does not appear. If the
situation for the North and South neighbours remains
as in Fig. 9, with 22 ways, we can say that there are
48 ways when v lies in only one M-segment interior, it
being vertical.
A similar argument shows that there are also
48 ways when v lies in only one M-segment
interior, it being horizontal. Taking into account the
16 combinations discussed above where v is a π-
vertex, we conclude that n1 = 48 + 48 + 16 = 112.
Furthermore, we have already shown that n0 + n1 +
n2 = 256. Therefore n0 = 128.
Thus we obtain from the n j table
µ
V
◦
M
=
128 ·0+112 ·1+16 ·2
256
=
9
16
.
Using Theorem 1 we can calculate µME and µMS for
this example as follows:
µME = 1+
2 · 9
16
4−2 · 9
16
=
32
23
,
µMS = 2
(
1+
2 · 9
16
− 1
16
·1
4−2 · 9
16
)
=
63
23
.

In some of our examples, for instance in the one
just analysed, we think that the entities µME and µMS
are more difficult to find than the entities µ ◦
VM
,µVL
and µ
V[π]
◦
M
on the right-hand-side of our Theorem’s
identities. In the next example, we acknowledge that
the reverse is true; a direct argument exists to find
µME and µMS without firstly evaluating the other three
entities.
Example 6. Brick wall with random H and
V chords: In this example a stationary brick-wall
tessellation (using ℓ× 1 bricks) is modified by the
independent insertion into each brick of n independent
random chords, sampled uniformly from the set of all
horizontal or vertical chords. See Fig. 10, where n = 3
and ℓ = 2; the chords are shown as white. The chord-
creation rule implies that chords are horizontal with
probability p given by Eq. 11, otherwise vertical.
p =
1
ℓ+1
. (11)
90
Image Anal Stereol 2018;37:83-98
Fig. 10. The bricks in Example 6, with white chords;
here ℓ= 2 and n = 3.
A B
CD
Fig. 11. One brick of Example 6 shown as the rectangle
ABCD; here n = 7.
Consider a typical brick b from the set B of bricks.
One rendition of b when n = 7 is the rectangle ABCD
in Fig. 11.
Define H(b) as the number of horizontal chords of
brick b; we note that H(b) is binomially distributed
with EB(H(b)) = np. Given H(b) = h, the number of
chord-crossings within b is h(n− h). Unconditionally,
the expected number is EB(h(n − h)) which equals
n(n−1)p(1− p).
Prior to the chords being added, each brick has six
vertices on its boundary but, in order to avoid triple
counting of these, we associate only two of these with a
particular brick; if b is ABCD in the figure, these are the
two vertices with large black dots. The 2n vertices with
smaller dots terminate the n chords whilst the vertices
at chord-crossings have no dot. The expected total
number of vertices associated with a brick is therefore
2+ 2n+ n(n− 1)p(1− p) of which 2+ 2n will be π-
vertices. So the vertex and π-vertex intensities are
λV = λBEB(2+2n+h(n−h))
= λB[2(n+1)+n(n−1)p(1− p)] , and
λV[π] = EB(2+2n) = 2λB(n+1) ,
where, because the brick has area ℓ, λB = 1/ℓ.
Therefore
φ =
2(n+1)
2(n+1)+n(n−1)p(1− p) and µVE = 4−φ ,
(12)
the latter result following because all π-vertices have
valency 3 and all non π-vertices have valency 4 in this
tessellation.
To obtain µVL, we note that no vertex lies on > 1
line; some (the grey dots and the two large black dots
in Fig. 11) lie on 1 line, others (the small black dots)
lie on no line. For brick b, given H(b) = h, the vertical
chords create 2(n− h) grey dots. So, given H(b) = h,
b contributes in total 2 + 2(n − h) vertices that are
adjacent to one line ∈ L. Unconditionally, we expect
the contribution from b to be EB(2+ 2n− 2h) = 2+
2n− 2np. Thus λV[L,1], the intensity of vertices lying
on exactly 1 line, is λB(2+2n−2np). Therefore
µVL =
λV[L,1]
λV
=
2(1+n−np)
2(n+1)+n(n−1)p(1− p)
=
2(1+ ℓ+ ℓn)(ℓ+1)
2(n+1)(ℓ+1)2+n(n−1)ℓ , using Eq. 11.
Likewise given H(b)= h, the brick b contributes h(n−
h) vertices (the chord crossings) lying in the interior
of two M-segments and 2h vertices (those small black
dots where a horizontal chord hits the boundary of b)
lying on just one M-segment interior. So, if we denote
the set of vertices lying in the interior of j M-segments
by V[
◦
M, j], then
λ
V[
◦
M, j]
= 0, if j ≥ 3,
λ
V[
◦
M,2]
= λB EB(h(n−h)) , and
λ
V[
◦
M,1]
= λB EB(2h) .
Thus
µ
V
◦
M
=
λ
V[
◦
M,1]
+2λ
V[
◦
M,2]
λV
=
EB(2h)+2EB(h(n−h))
2(n+1)+n(n−1)p(1− p)
=
2np+2n(n−1)p(1− p)
2(n+1)+n(n−1)p(1− p)
=
2n(ℓ+1+ ℓ(n−1))
2(n+1)(ℓ+1)2+n(n−1)ℓ .
With similar accountancy,
λ
V[π][
◦
M,1]
= EB(2h) = 2npλB , and
λ
V[π][
◦
M, j]
= 0 if j > 1 .
91
COWAN R ET AL: Unions of tessellation edges
Therefore
µ
V[π]
◦
M
=
λ
V[π][
◦
M,1]
λV[π]
=
np
n+1
=
n
(n+1)(ℓ+1)
.
Application of Eqs. 9 and 10 in Theorem 1 gives
values for µME and µMS.
µME = 1+
2n(1+ ℓn)
(n+1)(1+ ℓ)2
µMS = 2+
2n(1− ℓ+2ℓn)
(n+1)(1+ ℓ)2
.
In Fig. 10, n = 3 and ℓ= 2; thus µME =
13
6
and µMS =
23
6
.
Checking these values: To calculate µME directly,
we say that each brick ‘owns’ n + 1 M-segments of
the tessellation. These are the n chords of the brick
together with the left side of the brick (the brick’s right
side being owned by the neighbouring brick). So a
typical M-segment of the tessellation can be found by
considering a typical brick b from the set B of bricks
and randomly selecting one of that brick’s n + 1 M-
segments.
Note that b’s left side is hit from the right direction
by an expected number np of chords. It is also hit
by an expected number np of chords from the left
direction (chords of the cell to b’s left). Thus b’s left
side comprises an expected 1+2np edges. Conditional
upon H(b) = h, there are h(n − h) crossings of b’s
chords and these chords contain a total of (h+ 1)(n−
h)+ h(n− h+ 1) = n+ 2nh− 2h2 edges, on average
(n + 2nh − 2h2)/n per chord. Unconditionally, the
expected number of edges on a random choice of chord
is EB(n+2nh−2h2)/n which can be evaluated easily,
because H(b)∼ Binomial[n, p]; it is 1+2(n−1)p(1−
p). Thus
µME =
1
n+1
(1+2np)+
n
n+1
(
1+2(n−1)p(1− p)
)
= 1+
2np
n+1
(
p+n(1− p)
)
= 1+
2n(1+ ℓn)
(n+1)(1+ ℓ)2
, using Eq. 11.
Similarly,
µMS =
1
n+1
(2+2np)+
n
n+1
(
2+4(n−1)p(1− p)
)
= 2+
2np
n+1
(
2p+2n(1− p)−1
)
= 2+
2n(1− ℓ+2ℓn)
(n+1)(1+ ℓ)2
.
Thus we get agreement with the values found by using
Theorem 1. 
PROOF PRELIMINARIES
The line-process component: At the outset in our
proofs, we must recognise that some tessellations
contain infinite unions of edges, these unions forming
lines which extend infinitely in both directions. A line
process and any tessellation constructed from a line
process by adding edges and vertices or by operations
like superposition or nesting, provide examples. Our
Fig. 1 has lines which traverse the window and we
ask the reader to think that some of these may extend
infinitely in both directions.
In general, we must keep track of the
complications that arise if the tessellation frame ̥
contains lines and, to this end, the following definition
is helpful.
Definition 8. The line-process component (LPC) of
a planar tessellation is the union of all edges which
are not contained in some M-segment or in some
half-line. Equivalently, the LPC is the closure of the
structure which remains after all M-segments and all
half-lines of the tessellation are removed. Of course,
many tessellations have no LPC so this remaining
structure is null in these cases. If non-null, it is a line
process comprising lines and the vertices formed by
their intersections (if any). The collection of all the
lines in the LPC gives us the set L defined and used
earlier.
An LPC comprising just one set of parallel lines
and therefore no line–intersections (or indeed other
vertices) is permitted; such a structure is not a
tessellation in our sense but it is a valid LPC (for
example, in the ‘brick wall’ tessellation, seen as the
black frame in Fig. 10).
The event {the LPC has three or more of its
lines passing through some point of the plane} has
probability zero in many studies of stationary line
processes, but there are exceptions (trivial examples
using a triangular lattice or complicated examples as
seen in Kallenberg (1977) and Mecke (1979) where
three or more lines cross at some vertices of a
stationary line process). The parameter µVL quantifies
the crossings of such lines, even in the exceptional
cases of Kallenberg and Mecke, and also deals with
the adjacencies between vertices and lines when other
tessellation vertices lie on the lines of the LPC.
There can be other complications when L is not
null: edges might be subsets of a line in L or subsets
92
Image Anal Stereol 2018;37:83-98
of an M-segment; vertices other than those from line-
crossings may lie on a line in L, on the interior of an
M-segment or on a terminus of an M-segment; some
of these might be π-vertices. Furthermore, a vertex of
the LPC might have non-LPC edges emanating from
it. We address these complications later in the paper,
in the course of proving Theorem 1.
Line-segment processes: Our aim now is to prove
that mention of half-lines in the subsection above is
unnecessary, because effectively they cannot exist in
stationary tessellations.
Some preliminaries concerning stationary
processes of line-segments are required for this
task. There are many such processes imbedded in
a stationary tessellation, for example, we have a
stationary process of edges – or of sides, or of M-
segments. Line-segment processes can exist, of course,
without the presence of a tessellation. A general
theory, albeit with an added assumption of isotropy
(statistical invariance under any planar rotation), was
given in Cowan (1979).
One particular formula from that study (his
formula (14) ) is useful here. A reference line L
of the plane, chosen without dependence on the line-
segment process, might cross some of the process’s
line-segments. The mean number crossed by a unit
interval on L was found to be
K λ ℓ̄ , (13)
where the constant K equals 2/π . Also λ is the generic
intensity of segment mid-points and ℓ̄ is the expected
length of the typical segment. Without isotropy, the
constant K is different, involving an integral of the
orientation distribution for the random line-segments
(see Chiu et al. (2013), formula (8.36)). This constant
is finite and positive, except when all the line-segments
of the process are parallel to the reference line; then it
is zero. So, in all but this case, the expected number
crossed by a unit interval on L is given by Eq. 13, for
some appropriate positive constant K.
Remark 6. When we consider a line-segment process
of edges in a stationary tessellation satisfying the
regularity conditions given in our Remark 3, then both
λE and ℓ̄E are positive and finite; also it is impossible
in a planar tessellation that all the edges can be
parallel. So the expected number of tessellation edges
crossed by a unit interval on L is given by Eq. 13, with
(λ , ℓ̄) = (λE, ℓ̄E). So this expected number is finite and
positive.
Remark 7. A half-line is defined as {v ∈ R2 : v =
a0 + ta1,a0,a1 ∈ R2, t ∈ [0,∞)}. The terminus of this
half-line is the point a0. A half-line contains an infinite
number of subsets which are half-lines. A maximal
half-line is a half-line that is not contained in any other
half-line.
Maximal half-lines non-existent?: We should
consider if unions of tessellation edges might form
a maximal half-line in the tessellation’s frame? The
following lemma shows, however, that we can dismiss
this idea. A stationary tessellation, conforming to the
conditions of Remark 3 and containing maximal half-
lines within its frame, has probability zero. So none of
the line-segments in Fig. 1, that have one end inside
the window and the other on the window’s boundary,
would have an infinite extension from the latter end
beyond the window. Also line-segments in the figure
which intersect with the window’s boundary at two
points are not a subset of maximal half-lines.
Lemma 3. The frame of any stationary tessellation,
having 0 < λE < ∞ and 0 < ℓ̄E < ∞, contains maximal
half-lines with probability zero.
Proof of Lemma 3: We assume the contrary
position: Let t be a stationary random tessellation
having 0 < λE < ∞ and 0 < ℓ̄E < ∞ whose frame ̥
contains maximal half-lines with probability p> 0. We
shall then establish a contradiction.
The termini of the maximal half-lines must, by the
stationarity of t, form a stationary point process in R2.
Imagine that we replace each maximal half-line
H by a line-segment ⊂ H of length c1 covering H’s
terminus. This exercise can be repeated progressively
doubling the lengths, c j = 2
j−1c1, j ≥ 1. For a given j,
the collection of these ‘replacement segments’ forms a
stationary line-segment process called S j.
Let L be a fixed reference line; we assume that
L is chosen without dependence on ̥. For example,
we cannot take the line that covers an edge of ̥
to be our L . Let I be a closed interval ⊂ L of
unit length. We define X j be the number of line-
segments of S j which hit I. The sequence of random
variables {X j} j≥1 is non-decreasing – once a line-
segment crosses I, it remains crossing. Note thatEX j ∼
2 j−1c1; see Eq. 13 and the discussion near it. So we
obtain lim j→∞EX j = ∞.
Of course, if all the (potential) half-lines created in
the random tessellation are parallel to our fixed L , the
argument above doesn’t apply. Then, the use instead
of any other reference line not parallel to L will close
this argument.
Now let X be a random variable given by the
number of intersection points on I generated by the
maximal half-lines of t. With Remark 6 we have
EX < ∞. For any realisation t of t and for all j
we have X j(t) ≤ X(t). That yields EX j ≤ EX . With
93
COWAN R ET AL: Unions of tessellation edges
lim j→∞EX j = ∞ this contradicts the finiteness of EX .
The supposed existence of maximal half-lines leads
to an infinite intensity of crossings of L whereas
our tessellations produce only finite intensities. The
contradiction implies that p cannot be positive. 
We can now delete the reference to (maximal) half-
lines in Definition 8. Maximal half-lines will not be
considered further in the sequel.
PROOF OF LEMMA 1 AND
THEOREM 1
Proof of Lemma 1: Located at a vertex v ∈ V are
edge-termini, each of these being a 0-face of an edge
which emanates from the vertex. The expected number
of edge-termini at the typical vertex is µVE and so
the intensity of edge-termini is µVE λV. These edge-
termini can be classified further. There are two for
each line that v lies on and, similarly, two for each M-
segment interior that v lies in. Furthermore, there is
one edge-terminus at v for every M-segment terminus
that v lies on. Therefore, recognising that ‘lying on’ or
‘lying in’ are adjacencies, we have an identity,
µVE = µVM0 +2(µ
◦
VM+µVL) ,
where M0 is the class of M-segment termini. Noting
that λM =
1
2
λM0 =
1
2
µVM0λV, we have the result in
Lemma 1, namely λM =
1
2
(µVE−2µ ◦VM−2µVL)λV. 
Proof of Theorem 1: We commence with the
exchange formula Eq. 7, setting X=M and Y = E,
µME =
λE
λM
µEM , (14)
and note that µEM, defined as the expected number of
M-segments adjacent to the typical edge e ∈ E, has
two other interpretations: firstly, it is the proportion
of edges that lie on M-segments; secondly, it is the
probability that the typical edge is contained in exactly
one M-segment. These interpretations follow because
the edges on the LPC lines are not contained in any M-
segment and the others are contained in exactly one.
Indeed µEL+µEM = 1, where µEL = PE{e is contained
in exactly one line of the LPC}. Thus, (14) becomes
µME =
1
2
λVµVE
1
2
(µVE−2µ ◦VM−2µVL)λV
(1−µEL)
=
µVE
µVE−2µ ◦VM−2µVL
(1−µEL) ,
where Lemma 1 provides λM. Using again the
accountancy applied in the proof of Lemma 1 and
the formula λEµEL = λVµVL, we can write µEL as
2µVL/µVE. Therefore Eq. 9, the first part of Theorem
1, is proved.
Consider now an M-segment comprising only
edges of type E[2], that is, those that equal two cell
sides (see Fig. 12 taken from Cowan and Thäle (2014)
where these edge types are introduced).
Note that k of these edges, and therefore the M-
segment, contains 2k sides. Obviously all k−1 vertices
in the interior of this M-segment are π̄-type. Now
add j π-vertices in the segment’s interior, positioned
arbitrarily (though not, of course, on top of the existing
π̄-vertices). As each π-vertex is added an extra edge
is formed and a side is split into two sides. So this
modified M-segment will comprise k + j edges and
2k + j sides. Note that the number of sides is twice
the number of edges minus the number of added π-
vertices. Thus we have
µMS = 2µME−µ ◦MV[π] , (15)
the second term being the expected number of
π-vertices adjacent to (that is, contained in) the
typical M-segment interior. From Eq. 7, λ ◦
M
µ ◦
MV[π] =
λV[π] µ
◦
V[π]M. Moreover, µ
◦
V[π]M equals zero if the π-
vertex lies on the LPC and equals one otherwise. Thus
µ ◦
MV[π] =
λV[π]
λ ◦
M
µ ◦
V[π]M =
φλV
λM
µ ◦
V[π]M ,
whereby Eq. 10 for µMS follows, via Eq. 15. 
EDGE SUBSETS
Fig. 12, taken from Cowan and Thäle (2014),
defines a classification of edges into subsets E[ j], j =
0,1,2 and it would be of interest to find µME[ j], the
expected number of edges of set E[ j] contained in the
typical M-segment.
We have found this entity (using Eq. 7 and Lemma
1) for tessellations with no LPC,
µME[ j] =
λE
λM
ε j =
µVE
µVE−2 µ
V
◦
M
ε j . (16)
The parameters ε j for j = 0,1,2, which have been
introduced in Cowan and Thäle (2014) and shown
to be fundamental parameters of non side-to-side
tessellations, are defined to be the proportion of edges
coinciding with j cell sides. So ε j := λE[ j]/λE and
ε0 + ε1 + ε2 = 1.
94
Image Anal Stereol 2018;37:83-98
E[2] E[1] E[0]
Fig. 12. In each of the four pictures, focus attention
on the horizontal edge whose termini are both in
view. This edge lies in the subsets shown schematically
below each picture. E[ j], j = 0,1,2 is the subset of
edges that are equal to j cell sides.
The epsilon values can be calculated for Example
5, by focusing on a pre-migration horizontal edge
e. Post-migration there are 42 equally-likely different
positions of e, but only 8 after reflection-symmetries,
about a line through e’s original position, are
considered. In seven of these eight, e must be of type
E[2] regardless of how nearby vertices migrate. In the
remaining one position, e now has a ±45◦ slope and it
is easily seen (by considering the migrations possible
for nearby vertices) that e is type E[2] with probability
9/16, type E[1] with probability 6/16 and type E[0]
with probability 1/16. So ε2 =
7
8
· 1 + 1
8
· 9
16
= 121
128
,
ε1 =
1
8
· 6
16
= 6
128
, whilst ε0 =
1
128
. So ,
{µME[2],µME[1],µME[0]}=
4
4−2 ·9/16{
121
128
, 6
128
, 1
128
}
= { 121
92
, 6
92
, 1
92
} ,
from Eq. 16.
The epsilon values are known for the STIT
tessellation. See section 6.3 of Cowan (2013). So from
Eq. 16, {µME[2],µME[1],µME[0]} equals
3
3−2 ·1{
1
3
(8log2), 2
3
(5−6log2), 2
3
(2log2−1)}
= {8log2, 2(5−6log2), 2(2log2−1)}
≈ {0.5452, 1.6822, 0.7726} .
The result in Eq. 16 could be extended to cover
cases with an LPC, but only if some further parameters
are introduced – and for simplicity we have elected not
to do this.
M-SEGMENTS IN TESSELLATIONS
GENERATED BY SUPERPOSITION
OR NESTING
We will apply our results now to tessellations
which can be generated by two important operations:
superposition and nesting. For definitions, notations
and early literature concerning these operations,
we follow Cowan and Thäle (2014). Some recent
applications of the operations can be seen in
Neuhäuser et al (2014).
In this section the two tessellations involved are
assumed to be independent and, to get reasonably
pleasant formulae, a further assumption is needed: at
least one of the tessellations should be isotropic.
It is difficult to find formulae for µME and µMS
for M-segments in a superposition or nesting using
a direct way of calculation. It is more advisable, we
think, to focus on the vertices and their properties in
the generated tessellation. From results for the typical
vertex, other quantities such as µME and µMS can be
calculated - as we have done in our main theorem.
The frame ̥ (the union of all edges) of a
tessellation can be separated into two sets M̥ and L̥,
the union of all M-segments and L-lines, respectively.
The corresponding length intensities (mean frame
length in any domain of unit area) are ℓ̥̄, ℓ̄ M̥ and ℓ̄ L̥ .
Obviously ̥ = M̥ ∪ L̥ and ℓ̥̄ = ℓ̄ M̥ + ℓ̄ L̥ . For all
notations related to the two tessellations we use an
upper index (1) and (2).
Superposition: The superposition of two tessellations
with frames ̥(1) and ̥(2) is a tessellation with frame
̥=̥(1)∪̥(2), whose vertex intensity is
λV = λ
(1)
V
+λ
(2)
V
+
2
π
ℓ̄
(1)
̥ ℓ̄
(2)
̥ .
All new vertices created by superposition (these
have vertex intensity 2 ℓ̄
(1)
̥ ℓ̄
(2)
̥ /π) are ×-vertices; a
superposition creates no new π-vertices. These new ×-
vertices can be classified into three subclasses, with
vertex intensities given below in brackets for each
class:
– vertices adjacent to two lines and to zero M-
segment interiors
(
2 ℓ̄
(1)
L̥
ℓ̄
(2)
L̥
/π
)
;
– vertices adjacent to one line and to one M-segment
interior
(
2(ℓ̄
(1)
L̥
ℓ̄
(2)
M̥
+ ℓ̄
(1)
M̥
ℓ̄
(2)
L̥
)/π
)
;
– vertices adjacent to zero lines and to two M-
segment interiors
(
2 ℓ̄
(1)
M̥
ℓ̄
(2)
M̥
/π
)
.
All M-segments and lines of the two tessellations
remain in the superposition and a superposition creates
no new M-segments, that is,
M̥ =̥
(1)
M
∪̥(2)
M
and L̥ =̥
(1)
L
∪̥(2)
L
.
95
COWAN R ET AL: Unions of tessellation edges
A superposition creates new vertices on lines and in
the interior of M-segments.
Using these properties we obtain the following results
– for the basic parameters µVE and φ :
µVE =
1
λV
(
λ
(1)
V
µ
(1)
VE
+λ
(2)
V
µ
(2)
VE
+4 · 2
π
ℓ̄
(1)
̥ ℓ̄
(2)
̥
)
φ =
1
λV
(
λ
(1)
V[π]
+λ
(2)
V[π]
)
,
– for the LPC-parameter µVL:
µVL =
1
λV
(
λ
(1)
V
µ
(1)
VL
+λ
(2)
V
µ
(2)
VL
+
2
π
(ℓ̄
(1)
L̥
ℓ̄
(2)
M̥
+ ℓ̄
(1)
M̥
ℓ̄
(2)
L̥
)
+
4
π
ℓ̄
(1)
L̥
ℓ̄
(2)
L̥
)
,
– for the M-segment parameters µ
V
◦
M
and µ
V[π]
◦
M
:
µ
V
◦
M
=
1
λV
(
λ
(1)
V
µ
(1)
V
◦
M
+λ
(2)
V
µ
(2)
V
◦
M
+
2
π
(ℓ̄
(1)
L̥
ℓ̄
(2)
M̥
+ ℓ̄
(1)
M̥
ℓ̄
(2)
L̥
)
+
4
π
ℓ̄
(1)
M̥
ℓ̄
(2)
M̥
)
.
Nesting: To describe nesting we again start with a
tessellation having frame ̥(1). For each cell z ∈ Z(1)
we independently generate a tessellation with frame
̥(2)(z) distributed as ̥(2) and add ̥(2)(z)∩z to ̥(1).
That means independent copies of ̥(2) are nested into
the cells of ̥(1). The nested tessellation has the frame
̥=̥(1)∪ ⋃
z∈Z(1)
(̥(2)(z)∩ z) and the vertex intensity
λV = λ
(1)
V
+λ
(2)
V
+
4
π
ℓ̄
(1)
̥ ℓ̄
(2)
̥ .
All new vertices in a nesting (they have intensity
4ℓ̄
(1)
̥ ℓ̄
(2)
̥ /π) are π-vertices with three emanating edges.
There are two subclasses:
– vertices which lie in the interior of one M-segment
of ̥(1) (their intensity is 4ℓ̄
(1)
M̥
ℓ̄
(2)
̥ /π),
– vertices which lie on one line of ̥(1) (their
intensity is 4ℓ̄
(1)
L̥
ℓ̄
(2)
̥ /π).
The lines and M-segments of ̥(1) remain, but the
nested structure can create new vertices on them. In
the interior of the cells of ̥(1) new M-segments occur.
The LPC of ̥(2) disappears, the nested tessellation
contains only lines from ̥(1). Using that we obtain
– for the basic parameters µVE and φ :
µVE =
1
λV
(
λ
(1)
V
µ
(1)
VE
+λ
(2)
V
µ
(2)
VE
+3 · 4
π
ℓ̄
(1)
̥ ℓ̄
(2)
̥
)
,
φ =
1
λV
(
λ
(1)
V[π]
+λ
(2)
V[π]
+
4
π
ℓ̄
(1)
̥ ℓ̄
(2)
̥
)
,
– for the LPC-parameter µVL:
µVL =
1
λV
(
λ
(1)
V
µ
(1)
VL
+
4
π
ℓ̄
(1)
L̥
ℓ̄
(2)
̥
)
,
– for the M-segment parameters µ
V
◦
M
and µ
V[π]
◦
M
:
µ
V
◦
M
=
1
λV
(
λ
(1)
V
µ
(1)
V
◦
M
+λ
(2)
V
(µ
(2)
V
◦
M
+µ
(2)
VL
)
+
4
π
ℓ̄
(1)
M̥
ℓ̄
(2)
̥
)
,
µ
V[π]
◦
M
=
1
λV[π]
(
λ
(1)
V[π]µ
(1)
V[π]
◦
M
+λ
(2)
V[π](µ
(2)
V[π]
◦
M
+µ
(2)
V[π]L)+
4
π
ℓ̄
(1)
̥ ℓ̄
(2)
̥
)
,
Using these results with Lemma 1 and Theorem
1 the characteristics of M-segments in tessellations
generated by superposition or nesting can be
calculated.
Examples of these operations: In order to show
some practical value, superposition and nesting are
now considered for an isotropic STIT tessellation and
an isotropic Poisson line tessellation (PLT). As a
scaling parameter we use that the mean area of the
typical cell in both tessellations is equal to one or
λ
(stit)
Z
= λ
(plt)
Z
= 1 .
Our compilation of the basic parameters of a STIT
tessellation (which we have discussed in Example 4;
see Fig. 5) are as follows. Details are omitted.
– A STIT tessellation has no LPC: ̥(stit) =̥
(stit)
M
.
– All vertices are π-vertices with three emanating
edges: φ (stit) = 1 and µ
(stit)
VE
= 3.
– Therefore µ
(stit)
V
◦
M
= µ
(stit)
V[π]
◦
M
= 1 and µ
(stit)
VL
= 0.
– With the scaling parameter we obtain further:
ℓ̄
(stit)
̥ = ℓ̄
(stit)
M̥
=
√
π, ℓ̄
(stit)
L̥
= 0 and λ
(stit)
V
= 2.
The basic parameters of a Poisson line tessellation are
as follows.
– A PLT has no M-segments: ̥(plt) =̥
(plt)
L
.
96
Image Anal Stereol 2018;37:83-98
– All vertices are ×-vertices, there are no π-vertices:
φ (plt) = 0 and µ
(plt)
VE
= 4.
– Therefore µ
(plt)
V
◦
M
= 0 and µ
(plt)
VL
= 2.
– With the scaling parameter we obtain further:
ℓ̄
(plt)
̥ = ℓ̄
(plt)
L̥
=
√
π , ℓ̄
(plt)
M̥
= 0 and λ
(plt)
V
= 1.
The following three examples for a STIT and a Poisson
line tessellation are considered.
Example 7. A superposition of a STIT and a PLT, see
Fig. 13, has the following parameters.
λV = 5 , φ =
2
5
, µVE =
18
5
,
µVL =
4
5
, µ
V
◦
M
=
4
5
, µ
V[π]
◦
M
= 1 .
Fig. 13. The superposition of a STIT tessellation (with
thin edges) and a Poisson line tessellation (thick lines).
With Lemma 1 and Theorem 1 the M-segment
characteristics are
λM = 1 , µME = 5 , µMS = 8 .
Example 8. A nesting of a STIT into the cells of a PLT,
see Fig. 14, creates a tessellation with the following
parameters
λV = 7 , φ =
6
7
, µVE =
22
7
,
µVL =
6
7
, µ
V
◦
M
=
2
7
, µ
V[π]
◦
M
=
2
6
.
Fig. 14. A STIT tessellation (with thin edges) nested
into a Poisson line tessellation (thick lines).
With Lemma 1 and Theorem 1 the M-segment
characteristics are
λM = 3 , µME =
5
3
, µMS =
8
3
.
Example 9. A nesting of a PLT into the cells of a STIT
tessellation, see Fig. 15, creates a nested tessellation
with no LPC having the following parameters.
λV = 7 , φ =
6
7
, µVE =
22
7
,
µVL = 0 , µ
V
◦
M
=
8
7
, µ
V[π]
◦
M
= 1 .
Fig. 15. A Poisson line tessellation (with thin edges)
nested into a STIT tessellation (thick lines).
With Lemma 1 and Theorem 1 the M-segment
characteristics are
λM = 3 , µME =
11
3
, µMS =
16
3
.
97
COWAN R ET AL: Unions of tessellation edges
SOME CONCLUDING COMMENT
1. For a tessellation where all M-segments are I-
segments and where all π-vertices have three
emanating edges we have
2λM = λV[π] = φλV ,
because the termini of an M-segment are π-
vertices and any π-vertex is a terminus of one M-
segment.
2. If the tessellation is side-to-side (that is, if φ = 0)
or if φ > 0 and all the π-vertices are lying on lines
(that is µ
V[π]
◦
M
= 0), then we have (using Theorem
1) that
µMS = 2µME .
3. Vertices in the interior of the typical M-segment:
µ ◦
MV
= µME − 1 and, with the exchange formula
Eq. 7 and Lemma 1,
µ ◦
MV[π]
=
φλV
λM
µ
V[π]
◦
M
= 2
φ µ
V[π]
◦
M
µVE−2(µ
V
◦
M
+µVL)
.
4. The proportions of edges which lie on M-segments
or on lines: Using Eq. 9 and Lemma 1, it follows
that
µEM =
λM
λE µME
=
µVE−2µVL
µVE
.
From the identity µEM+ µEL = 1, we have µEL =
2 µVL/µVE .
5. The proportions of cell-sides which lie on M-
segments or on lines: Using Eqs. 3 and 10 for
φ > 0,
µSM =
λM
λS
µMS =
µVE−2µVL−φ µ
V[π]
◦
M
µVE−φ
.
From µSM+µSL = 1 and µ
V[π]
◦
M
+µV[π]L = 1, we
can write µSL = (2µVL−φ µV[π]L)/(µVE−φ).
ACKNOWLEDGEMENT
We thank both referees for their careful reading of
our paper and for their excellent suggestions.
REFERENCES
Blizard WD (1989). Multiset Theory. Notre Dame J Form L
30:36–66.
Chiu SN, Stoyan D, Kendall WS, Mecke J (2013).
Stochastic Geometry and its Applications. 3rd Ed.
Chichester: Wiley.
Cowan R (1978). The use of ergodic theorems in random
geometry. Suppl Adv Appl Probab 10:47–57.
Cowan R (1979). Homogeneous line-segment processes.
Math Proc Cambridge 86:481–9.
Cowan R (1980). Properties of ergodic random mosaic
processes. Math Nachr 97:89–102.
Cowan R (2010). New classes of random tessellations
arising from iterative division of cells. Adv Appl Probab
42:26–47.
Cowan R (2013). Line-segments in the isotropic planar STIT
tessellation. Adv Appl Probab 45:295–311.
Cowan R, Thäle C (2014). The character of planar
tessellations which are not side-to-side. Image Anal
Stereol 33:39–54.
Cowan R, Weiss V (2015). Constraints on the fundamental
topological parameters of spatial tessellations. Math
Nachr 288:540–65.
Gilbert EN (1967). Surface films of needle-shaped crystals.
In: Noble B, Ed. Applications of undergraduate
mathematics in engineering, 329–46. New York:
Macmillan.
Kallenberg O (1977). A counterexample to R. Davidson’s
conjecture on line processes. Math Proc Cambridge
82:301–7.
Kline M (1980). Mathematics: The loss of certainty. Oxford:
Oxford University Press.
Mackisack M, Miles RE (1996). Homogeneous rectangular
tessellations. Adv Appl Probab 28:993–1013.
Mecke J (1979). An explicit description of Kallenberg’s
lattice type point process. Math Nachr 89:185–95.
Mecke J, Nagel W, Weiss V (2007). Length distributions
of edges in planar stationary and isotropic STIT
tessellations. J Contemp Math Anal 42:28–43.
Mecke J, Nagel W, Weiss V (2011). Some distributions
for I-segments of planar random homogeneous STIT
tessellations. Math Nachr 284:1483–95.
Miles RE, Mackisack M (2002). A large class of
random tessellations with the classic Poisson polygon
distributions. Forma 17:1–17.
Muche L (2005). The Poisson-Voronoi tessellation. Adv
Appl Probab 37:279–96.
Neuhäuser D, Hirsch C, Gloaguen C, Schmidt V (2014).
Ratio limits and simulation algorithms for the Palm
version of stationary iterated tessellations. J Stat
Comput Sim 84:1486–504.
Schneider R, Weil W (2008). Stochastic and integral
geometry. Berlin: Springer.
Weiss V, Cowan R (2011). Topological relationships in
spatial tessellations. Adv Appl Probab 43:963–84.
98