Tessellations derived from random geometric graphs

Richard Cowan, Albert K. L. Tsang

Published 2016-06-06Version 1

In this paper we consider a random partition of the plane into cells, the partition being based on the nodes and links of a {\it random planar geometric graph}. The resulting structure generalises the \emph{random \tes}\ hitherto studied in the literature. The cells of our partition process, possibly with holes and not necessarily closed, have a fairly general topology summarised by a functional which is similar to the Euler characteristic. The functional can also be extended to certain cell-unions which can arise in applications. Vertices of all valencies, $0, 1, 2, ...$ are allowed. Many of the formulae from the traditional theory of random tessellations with convex cells, are made more general to suit this new structure. Some motivating examples of the structure are given.