Computing Klee's measure of grounded boxes (Q2346960): Difference between revisions

In the paper the authors study Klee's measure problem, i.e., given a set of \(n\) axis-aligned boxes in \(d\)-space, compute the volume of their union. They present a new result for Klee's measure under the assumption that a \(2\)-dimensional orthogonal projection of all the boxes has a common corner (\(2\)-grounded boxes). The general form of the proposed method is the following. Firstly, the \(d\)-dimensional problem is transformed into one of maintaining its \((d-1)\)-dimensional cross-section with a sweeping plane, and next this \((d-1)\)-dimensional problem is transformed into a \((d-2)\)-dimensional weighted volume problem. In this problem, each box has a non-negative weight and the contribution of each point in space equals the weight of the heaviest box containing it. At the beginning the authors describe how to transform the \(d\)-dimensional problem into an \((d-2)\)-dimensional weighted volume problem. To solve the transformed problem the authors firstly present an algorithm in the case of two-dimensional space and halfspaces, and then its generalization to higher dimensions. Next, they describe how to solve the general weighted volume by combining the halfspaces problem with a space partition technique. The proposed algorithm works in \(O(n^{(d-1)/2} \log^2 n)\) time and uses \(O(n^{(d-1)/2})\) space.