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.