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).