On the Largest Empty Axis-Parallel Box Amidst n Points

We give the first efficient (1?ε)-approximation algorithm for the following problem: Given an axis-parallel d-dimensional box R in ? ^d containing n points, compute a maximum-volume empty axis-parallel d-dimensional box contained in R. The minimum of this quantity over all such point sets is of the order $\Theta (\frac {1}{n} )$ . Our algorithm finds an empty axis-aligned box whose volume is at least (1?ε) of the maximum in O((8edε ^?2) ^d ?nlog ^d n) time. No previous efficient exact or approximation algorithms were known for this problem for d≥4. As the problem has been recently shown to be NP-hard in arbitrarily high dimensions (i.e., when d is part of the input), the existence of an efficient exact algorithm is unlikely. We also present a (1?ε)-approximation algorithm that, given an axis-parallel d-dimensional cube R in ? ^d containing n points, computes a maximum-volume empty axis-parallel hypercube contained in R. The minimum of this quantity over all such point sets is also shown to be of the order $\Theta (\frac{1}{n} )$ . A faster (1?ε)-approximation algorithm, with a milder dependence on d in the running time, is obtained in this case.