Computational Geometry Column 69

摘要

We revisit the following problem called Maximum Empty Box: Given a set S of n points inside an axis-parallel box U in R~d, find a maximum-volume axis-parallel box that is contained in U but contains no points of S in its interior. (I) We first present an algorithm that finds a relatively large empty box amidst n points in [0,1]~d, i.e., one whose volume is at least (log d)/(4(n+log d)). The algorithm is implicit in recent work of Aistleitner, Hinrichs, and Rudolf (2015); it is then verified that this task can be accomplished in O(n + d log d) time. (II) To better analyze the above approach, we introduce the notions of perfect vector sets and properly overlapping partitions, in connection to the minimum volume of a maximum empty box amidst n points in the unit hypercube [0,1]~d. It turns out that the minimum volume of the largest empty box is related to the maximum sizes of the aforementioned combinatorial objects.