should lead to better spatial spread.

Finally, PivotMDS is an approximation algorithm for multidimensional scaling that is based on sampling; for a detailed description the reader is referred to Brandes and Pich [@brandes].

Preliminary experiments indicated that PivotMDS and the random hypersphere approach fare similarly well. Since PivotMDS turned out to be more robust in terms of solution quality when applied to protein instances, we use it in all the following experiments. Its slower speed is more than outweighed by the more expensive maxent-stress algorithm.

##### Approximating the entropy term. {#approximating-the-entropy-term. .unnumbered}

The entropy term in Eq. (\[eq:maxent-stress\]) iterates over all elements not in $S$. As the set $S$ is usually sparse, this computation would thus require quadratic running time. Thus, it is important to approximate the distances required for the entropy calculations. We implemented both the well-known Barnes-Hut approximation (also used by Gansner [*et al.*]{}) as well as well-separated pair decomposition (WSPD) [@callahan1995].

Additionally, we evaluate the entropy lazily: instead of computing the entropy term in each iteration, we recompute it only when the function $\lfloor 5 \log i\rfloor$ changes, where $i$ is the iteration number. We expect the entropy term to significantly change more frequently at the beginning 