Details of implementation
The mosaic algorithm requires O(p 3) comparisons where p is the point (= vertex) count. It can be speeded up to O(p 2) by only examining edges connecting nearby pairs. Specifically, if i and j are the endpoints, then ifi is one of the 20-odd nearest neighbours of j , the edge should be examined; and vice versa. The reason for the cutoff of 20 is that in the final mosaic, no matter how computed, edges are usually short and points are always sparsely connected (Fig. 2). This algorithm will skip an edge if there are two or more large and tight clusters of points each having more points than the cutoff, in which case the user needs to decide whether a higher one should be imposed. The neighbours-only algorithm speeds up the calculations so much that a mosaic of 400 points can be arranged within about a second on a laptop computer. A simulation producing 1000 sets of 20-point mosaics takes about four seconds.
Outliers and long edges can of course inflate area estimates. A good, simple means of handling this problem is to exploit the preceding algorithm. Instead of only examining edges if either point is in the neighbourhood of the other point, one can require that each point is in the other’s neighbourhood. This ”mutual neighbour” criterion leads to removing edges that go to individual outliers or small clusters of outliers, in addition to long edges between large groups of outliers. It is used as the default in the analyses reported here.
Although computing a high-dimensional mosaic graph is trivial, the multiplication and summation procedure only yields a sensible estimate if there are two dimensions. A good solution is to compute mosaic areas for all pairs of dimensions; multiply them; and raise the value to the 1/P power where P is the number of pairs. For example, in two dimensions the power is 1, and in three it is 1/3 because there are three pairs. This is analogous to projecting a high-dimensional shape on to each side of a hypercube, averaging the projected areas, and using that as a proxy for the shape’s hypervolume. Although irrelevant to most ecological problems, this potential implementation makes the mosaic approach more useful in trait space analysis and morphometrics.