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.
approximation algorithm largest empty box largest empty hypercube discrepancy of a set of points van der corput point set halton-hammersley point set data mining