Mosaic algorithm
The divisive algorithm implemented by the mosaic package’s function mgraph produces mosaics with small sums of edge lengths, and is as follows. (1) All points (= vertices) are connected to all other points. (2) The edges are ordered from longest to shortest and inspected in turn. (3) If (a) the two connected points i andj are both connected to a third point and if (b) i andj are each connected to at least three points in total, then the edge is broken. If not, then it is kept.
For example, suppose there is a triangle. No edges can be broken because no point is connected to more than two others. If instead there are four points, at first each of them is connected to three others, so the longest edge (say, between points 1 and 4) is examined and discarded. Points 2 and 3 are now still triple junctions. Furthermore, each connects to the other via both 1 and 4. Therefore, the edge between 2 and 3 is also broken, resulting in a quadrilateral.
Two examples of mosaics produced by this algorithm are shown in Figs. 2A and B. As predicted, the number of edges connecting to each point is most often two, frequently three, occasionally four, and very rarely five or more. Lines very rarely cross. The algorithm occasionally creates a line at the outline of the overall shape that connects two pieces instead of belonging to a piece itself. There happens to be an example at the lower right of Fig. 2A. The method handles internal gaps in ranges well specifically because it rarely draws an edge across a gap, as long as there are enough surrounding points to complete a short circuit (Fig. 2B). Drawing squares around the edges makes it easier to visualise the contribution of each edge to the overall area estimate (Figs. 2C, D).