A Fast Exact Algorithm for Computing the Hypervolume Contributions in 4-D Space
提出一种O(n³²log n)时间的精确算法，用于计算四维空间中n个点的超体积贡献，比现有最优算法快O(n log n)，并采用空间分区策略降低实际运行时间和空间开销。
The hypervolume contribution is widely used in indicator-based multiobjective algorithms. We propose an algorithm to compute exact 4-D hypervolume contributions for a set of n points in O(n32logn) time. Our algorithm improves the currently best time complexity O(n2) by O(nlogn), 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.