Let B be a set of n axis-parallel boxes in d-dimensions such that each box has a corner at the origin and the other corner in the positive quadrant, and let k be a positive integer. We study the problem of selecting k boxes in B that maximize the volume of the union of the selected boxes. The research is motivated by applications in skyline queries for databases and in multicriteria optimization, where the problem is known as the hypervolume subset selection problem. It is known that the problem can be solved in polynomial time in the plane, while the best known algorithms in any dimension d>2 enumerate all size-k subsets. We show that: * The problem is NP-hard already in 3 dimensions. * In 3 dimensions, we break the enumeration of all size-k subsets, by providing an n^O(sqrt(k)) algorithm. * For any constant dimension d, we give an efficient polynomial-time approximation scheme.
@cite_30: The goal of multiobjective optimization is to find a set of best compromise solutions for typically conflicting objectives. Due to the complex nature of most real-life problems, only an approximation to such an optimal set can be obtained within reasonable (computing) time. To compare such approximations, and thereby the performance of multiobjective optimizers providing them, unary quality measures are usually applied. Among these, the hypervolume indicator (or S-metric) is of particular relevance due to its favorable properties. Moreover, this indicator has been successfully integrated into stochastic optimizers, such as evolutionary algorithms, where it serves as a guidance criterion for finding good approximations to the Pareto front. Recent results show that computing the hypervolume indicator can be seen as solving a specialized version of Klee's measure problem. In general, Klee's measure problem can be solved with O(n logn + nd 2logn) comparisons for an input instance of size n in d dimensions; as of this writing, it is unknown whether a lower bound higher than Omega(n log n) can be proven. In this paper, we derive a lower bound of Omega(n log n) for the complexity of computing the hypervolume indicator in any number of dimensions d > 1 by reducing the so-called uniformgap problem to it. For the 3-D case, we also present a matching upper bound of O(n log n) comparisons that is obtained by extending an algorithm for finding the maxima of a point set.
@cite_5: Klee’s Measure Problem (KMP) asks for the volume of the union of n axis-aligned boxes in ℝ d . Omitting logarithmic factors, the best algorithm has runtime ( O ^*(n^ d 2 ) ) [Overmars,Yap’91]. There are faster algorithms known for several special cases: Cube-KMP (where all boxes are cubes), Unitcube-KMP (where all boxes are cubes of equal side length), Hypervolume (where all boxes share a vertex), and k -Grounded (where the projection onto the first k dimensions is a Hypervolume instance).
@cite_8: We present a new algorithm for a classic problem in computational geometry, Klee's measure problem: given a set of n axis-parallel boxes in d-dimensional space, compute the volume of the union of the boxes. The algorithm runs in O(nd 2) time for any constant d ≥ 3. Although it improves the previous best algorithm by “just” an iterated logarithmic factor, the real surprise lies in the simplicity of the new algorithm. We also show that it is theoretically possible to beat the O(nd 2) time bound by logarithmic factors for integer input in the word RAM model, and for other variants of the problem. With additional work, we obtain an O(nd 3 polylog n)-time algorithm for the important special case of orthants or unit hypercubes (which include the so-called “hypervolume indicator problem”), and an O(n(d+1) 3 polylog n)-time algorithm for the case of arbitrary hypercubes or fat boxes, improving a previous O(n(d+2) 3)-time algorithm by Bringmann.
* Klee's Measure Problem To compute the volume of the union of @math (not necessarily anchored) axis-aligned boxes in @math is known as Klee's measure problem. The fastest known algorithm takes time In @math -notation, we always assume @math to be a constant, and @math is to be understood as @math . @math , which can be improved to @math if all boxes are cubes @cite_8 . By a simple reduction @cite_5 , the same running time as on cubes can be obtained on anchored boxes, which can be improved to @math for @math @cite_30 . These results are relevant to this paper because Klee's measure problem on anchored boxes (spanned by the points in @math ) is a special case of (by calling @math ).