Perfect vector sets, properly overlapping partitions, and largest empty box

Abstract

We revisit the following problem (along with its higher dimensional variant): Given a set $S$ of $n$ points inside an axis-parallel rectangle $U$ in the plane, find a maximum-area axis-parallel sub-rectangle that is contained in $U$ but contains no points of $S$. (I) We present an algorithm that finds a large empty box amidst $n$ points in $[0,1{]}^d$: a box whose volume is at least $\frac{\log d}{4(n+\log d)}$ can be computed in $O(n+d\log d)$ time. (II) To better analyze the above approach, we introduce the concepts 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$, and derive bounds on their sizes.

14 pages, 1 figure; updated bibliography and note added at the end of Section 7

References in corpus (1)

• Querying for the Largest Empty Geometric Object in a Desired Location