Empty axis-parallel boxes

DOI10.1093/IMRN/RNAB123MaRDI QIDQ5038049zbMATH OpenOpenAlexFDO

Authors Boris Bukh, Ting-Wei Chao

Publication date 29 September 2022

Published in IMRN. International Mathematics Research Notices (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.05820

zbMATH Keywords

dispersion

Mathematics Subject Classification ID

Length, area and volume in real or complex geometry (51M25) Erd?s problems and related topics of discrete geometry (52C10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We show that, for every set of $n$ points in the $d$-dimensional unit cube, there is an empty axis-parallel box of volume at least $Omega(d/n)$ as $noinfty$ and $d$ is fixed. In the opposite direction, we give a construction without an empty axis-parallel box of volume $O(d^{2}logd/n)$. These improve on the previous best bounds of $Omega(logd/n)$ and $O(2^{7d}/n)$ respectively.

Recommendations

• On the size of the largest empty box amidst a point set
• On the largest empty axis-parallel box amidst \(n\) points
• scientific article; zbMATH DE number 4178817
• On the Number of Maximum Empty Boxes Amidst n Points
• On the number of maximum empty boxes amidst \(n\) points

Cited in

(12)

• Containment problems in high-dimensional spaces
• On the largest empty axis-parallel box amidst \(n\) points
• Digital almost nets
• New bounds on the minimal dispersion
• On the size of the largest empty box amidst a point set
• The area of empty axis-parallel boxes amidst 2-dimensional lattice points
• Piercing random boxes
• scientific article; zbMATH DE number 4178817 (Why is no real title available?)
• Piercing all translates of a set of axis-parallel rectangles
• A tight lower bound on the minimal dispersion
• Minimal dispersion on the cube and the torus
• Lower bounds on the minimal dispersion of point sets via cover-free families

This page was built for publication: Empty axis-parallel boxes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5038049)