A Fast Exact Algorithm for Computing the Hypervolume Contributions in 4-D Space

—The hypervolume (HV) contribution is widely used in indicator-based multiobjective algorithms. We propose an algorithm to compute exact 4-D HV contributions for a set of n points in O(n^[3/^2] log n) time. Our algorithm improves the currently best time complexity O(n²) by O(√n/log n), and it is the first algorithm of subquadratic time for this problem. Our algorithm is built upon a space partition method in computational geometry and a geometric structure called the anchored gradient. We also propose a new space partition strategy to reduce the practical running time and the space overhead of this algorithm. Experimental results on a variety of test instances show that our proposed algorithm performs better than the existing state-of-the-art algorithm, especially, on point sets with cliff or other irregular properties.