We revisit a classical problem in computational geometry: finding the largest-volume axis-aligned empty box (inside a given bounding box) amidst n given points in d dimensions. Previously, the best algorithms known have running time O(n log^2 n) for d = 2 (by Aggarwal and Suri [SoCG'87]) and near n^d for d >= 3. We describe faster algorithms with running time
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(n^{d/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(n^{d/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(n^{d/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.
Given a set P of n points in R^d, where each point p of P is associated with a weight w(p) (positive or negative), the Maximum-Weight Box problem consists in finding an axis-aligned box B maximizing the sum of w(p) over all points p in B. We describe algorithms for this problem in two dimensions that run in the worst case in O(n^2) time, and much less on more specific classes of instances. In particular, these results imply similar ones for the Maximum Bichromatic Discrepancy Box problem. These improve by a factor of log n on the best worst-case complexity previously known for these problems, O(n^2 lg n) [Cortes et al., J. Alg., 2009; Dobkin et al., J. Comput. Syst. Sci., 1996].
Given n axis-parallel boxes in a fixed dimension d >= 3, how efficiently can we compute the volume of the union? This standard problem in computational geometry, commonly referred to as Klee's measure problem, can be solved in time O(n^{d/2} log n) by an algorithm of Overmars and Yap (FOCS 1988). We give the first (albeit small) improvement: our new algorithm runs in time n^{d/2} 2^{O(log* n)}, where log* denotes the iterated logarithm.
For the related problem of computing the depth in an arrangement of n boxes, we further improve the time bound to near O(n^{d/2} / log^{d/2-1} n), ignoring log log n factors. Other applications and lower-bound possibilities are discussed. The ideas behind the improved algorithms are simple.
We give space-efficient geometric algorithms for two related problems. Given a set of n axis-aligned rectangles in the plane, we calculate the area covered by the union of these rectangles (Klee's measure problem) in O(n^{3/2} log n) time with O(sqrt{n}) extra space. If the input can be destroyed and there are no degenerate cases and input coordinates are all integers, we can solve Klee's measure problem in O(n log^2 n) time with O(log^2 n) extra space. Given a set of n points in the plane, we find the axis-aligned unit square that covers the maximum number of points in O(n log^3 n) time with O(log^2 n) extra space.
The documents contained in this directory are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.