A Fast Dimension-Sweep Algorithm for the Hypervolume Indicator in Four Dimensions

Abstract

The Hypervolume Indicator is one of the most widely used quality indicators in Evolutionary Multiobjective Optimization. Its computation is a special case of Klee’s Measure Problem (KMP) where the upper end of all rectangular ranges coincides with a given reference point (assuming minimization, without loss of generality). Although the time complexity of the hypervolume indicator in two and three dimensions is known to be ( n logn), improving upon the O(n d=2 logn) complexity of Overmars and Yap’s algorithm for the general KMP in higher dimensions has been a challenge. In this paper, a new dimension-sweep algorithm to compute the hypervolume indicator in four dimensions is proposed, and its complexity is shown to be O(n 2 ).