2009/09/16 by Adrian Dumitrescu, Dumitrescu, Adrian, Minghui Jiang +1 · 1 citation
Computer Science · Engineering · Mathematics · #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Mathematical Approximation and Integration #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.0909.3127
openalex publication_date 2009/09/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We give the first nontrivial upper and lower bounds on the maximum volume of an empty axis-parallel box inside an axis-parallel unit hypercube in \RRd containing n points. For a fixed d, we show that the maximum volume is of the order Θ((1)/(n)). We then use the fact that the maximum volume is Ω((1)/(n)) in our design of the first efficient (1-\eps)-approximation algorithm for the following problem: Given an axis-parallel d-dimensional box R in \RRd containing n points, compute a maximum-volume empty axis-parallel d-dimensional box contained in R. The running time of our algorithm is nearly linear in n, for small d, and increases only by an O(logn) factor when one goes up one dimension. 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 arbitrary high dimensions (i.e., when d is part of the input), the existence of efficient exact algorithms is unlikely. We also obtain tight estimates on the maximum volume of an empty axis-parallel hypercube inside an axis-parallel unit hypercube in \RRd containing n points. For a fixed d, this maximum volume is of the same order order Θ((1)/(n)). A faster (1-\eps)-approximation algorithm, with a milder dependence on d in the running time, is obtained in this case.