Algorithms: Dominance Tree

@article{ dominance-tree,
    author      = {Hongbing Fang and Qian Wang
                   and Yi-Cheng Tu and Mark F. Horstemeyer},
    title       = {An Efficient Non-dominated Sorting Method
                   for Evolutionary Algorithms},
    journal     = {Evolutionary Computation},
    year        = {2008},
    volume      = {16},
    number      = {3},
    pages       = {355-384},
    publisher   = {MIT Press},
    langid      = {english}
}

How to get an instance:

• DominanceTree.getNoPresortInsertion(boolean useRecursiveMerge) -- returns an instance which uses neither preliminary lexicographical sorting of points, nor so-called "delayed insertion". If useRecursiveMerge is true, then merge operations on multiple trees are done as in mergesort, which appears to influence running times positively.
• DominanceTree.getPresortInsertion(boolean useRecursiveMerge, boolean useDelayedInsertion) -- returns an instance which uses preliminary lexicographical sorting of points. The useDelayedInsertion argument controls "delayed insertion".

Currently it appears that the getPresortInsertion(true, true) performs slightly better than other choices from this algorithm, apart from smallest numbers of points (say, 10), but when all the points have the same rank, the first argument set to false might behave slightly better (by maybe a few percent).

All versions require O(N) memory. They seem to have O(MN^2) worst-case running time complexity, although the proof in the paper is not strict enough to say it confidently. Presort versions are courtesy of this project since this possibility is not discussed in the original paper. Delayed insertion is currently not implemented for the no-presort version, as the paper did not make it clear, and I had troubles understanding how to implement it.