Requisite graph theory
The lengths of the edges in a mosaic graph M are used to obtain a single area estimate. Specifically, the procedure is to sum the lengths, square the sum, divide by the number of edges e to obtain a value notated LM 2/e , and then multiply the value by a constant derived below. The equation is implemented by the mosaic function mgraph .
A minimum spanning tree (MST) could be used for the same purpose. I discuss this idea in more detail later. MSTs are well-known and can be computed by using any of several algorithms, including a classic one proposed by Kruskal (1956). Shape area does scale tightly to the proposed function of the MST’s edge lengths. For example, supposep points (= vertices) are perfectly spaced on a square grid with the grid squares having edges of length a , yielding pa 2 as the shape’s area. Keeping in mind that there are always p – 1 edges in an MST, the sum is (p– 1) a ; the square is (p ­– 1)2a 2; and that divided by p is close top a 2 no matter what the MST’s shape.
However, real-world patterns are not grids. So in order to generalise, we need to switch from regular patterns to arbitrary distributions and discuss the theory of mosaic graphs. In a mosaic, (1) each point is connected to at least two others, and (2) no two points remain directly connected if some other point connects to both of them. Isolated triangles at the edges of the mosaic are allowed by this rule. However, on average, each empty loop (mosaic piece) is an octagon, there are four edges per piece, and there are five edges for every four points.
To understand why, note that adding any point inside an n -gon making up a mosaic piece either splits it or increases its edge count by one (Fig. 1). Suppose A is new, with nearest neighbours B and C. If B and C are adjacent, the A–B and A–C edges will be retained but the B–C edge will be discarded, increasing the mosaic piece’s size. If not, then the B–A–C edges will form a wall between two new pieces. Any larger pattern will have a greater risk of splitting. Thus, the growth and splitting processes will always push mosaic pieces towards a point count that happens to be balanced around eight (caption of Fig. 1).
Whenever a piece grows, a double junction forms at point A and an edge is removed. A double junction is still created in the equally likely splitting case, but the junctions at B and C each add one edge. On average, then, a new point creates one double junction and increases the edge count (degree) of one other point. The degree of a point rarely goes past three because any new point close to a triple junction will likely pair with two of the three edges leading to it, resulting in the loss of one edge.
Thus, on average, half of the points in a mosaic are of order two and half of order three. If the order is two there is one edge per point overall, as in a simple loop, and if three, there are 1.5 per point. Therefore, the ratio of edges to points is 1.25:1, or five to four, and of points to edges, 0.8. Because every edge inside a mosaic is shared by two pieces by definition, there are four edges per piece on average. Thus, there are 3.2 points per piece. These predictions are easily confirmed by simulation using the mosaic assembly algorithm described below.