This paper presents a recursive, dimension-sweep algorithm for computing the hypervolume indicator of the quality of a set of n non-dominated points in d > 2 dimensions. It improves upon the existing HSO (Hypervolume by Slicing Objectives) algorithm by pruning the recursion tree to avoid repeated dominance checks and the recalculation of partial hypervolumes. Additionally, it incorporates a recent result for the three-dimensional special case. The proposed algorithm achieves O(n d−2 log n) time and linear space complexity in the worst-case, but experimental results show that the pruning techniques used may reduce the time complexity exponent even further.
No takes yet. Share an insight, caveat, or question.
Fonseca et al. (2006) studied this question.
Synapse has enriched 3 closely related papers on similar clinical questions. Consider them for comparative context: