A Danzer set for axis parallel boxes

DOI10.1090/PROC/12911MaRDI QIDQ2796746zbMATH OpenOpenAlexFDO

Authors David Simmons, Yaar Solomon

Publication date 29 March 2016

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.0926, https://eprints.whiterose.ac.uk/112578/2/doc.pdf

zbMATH Keywords

admissible latticealigned boxescodiameterDanzer setdense forestGalois embeddingsgrowth ratering of integersvolume

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) General topics of discrete mathematics in relation to computer science (68R01)

Abstract: We present concrete constructions of discrete sets in $mathbb{R}^d$ ($dge2$) that intersect every aligned box of volume $1$ in $mathbb{R}^d$, and which have optimal growth rate $O(T^d)$.

Review text

The starting point of the authors is the question whether a discrete Danzer set in \(\mathbb{R}^d\) of growth rate \(O(T^n)\) exists. Remember that \(D\subseteq \mathbb{R}^n\) is a Danzer set whenever, for some \(s>0\), \(D\) intersects every convex set of volume \(s\). Their approach to this problem consists of considering a smaller family of sets, the align-Danzer sets (intersecting every aligned box \([a_1,b_1]\times\cdots\times[a_n,b_n]\) of volume \(s\)). In this setting, they provide concrete constructions of discrete align-Denzer sets having growth rate \(O(T^n)\).NEWLINENEWLINEWhen \(n=2\) they give (Theorem 1.1) an align-Danzer set which is a variant of the binary version of van der Corput sequence (see [\textit{J. G. van der Corput}, Proc. Akad. Wet. Amsterdam 38, 813--821 (1935; Zbl 0012.34705)]), having growth rate \(O(T^2).\) According to the authors, ``although the set \(D\) in Theorem 1.1 is given very explicitly, and the proof is by elementary means, it only solves the problem in dimension \(2\), and no simple higher-dimensional extension comes to mind, so in higher dimensions (Theorem 1.3) they opt for an approach based on admissible lattices in \(\mathbb R^n.\) Again, the construction is not new (in fact, their Theorem 1.3 is immediate from Theorem 1.2 in [\textit{M. M. Skriganov}, Invent. Math. 132, No. 1, 1--72 (1998; Zbl 0902.11041)]), but their merit relies on the fact of connecting these sets with Danzer's problem. Finally, applying the above results they reprove a result in computational geometry, namely, Corollary 1.4: For every \(\varepsilon >0\) there are \(\varepsilon\)-nets of optimal sizes \(O(1/\varepsilon)\) for the range space \((X,\mathcal{R})\), being \(X\) the \(n\)-dimensional cube and \(\mathcal{R}\) the set of aligned boxes.

Recommendations

• Dense forests and Danzer sets
• Around the Danzer problem and the construction of dense forests
• A note about weak -nets for axis-parallel boxes in d-space
• Efficient construction of a small hitting set for combinatorial rectangles in high dimension
• A dynamical system using the Voronoï tessellation
• Danzer's problem, effective constructions of dense forests and digital sequences
• On the number of unit-area triangles spanned by convex grids in the plane
• Towards Faster Linear-Sized Nets for Axis-Aligned Boxes in the Plane
• Dispersion of digital \((0,m,2)\)-nets
• scientific article; zbMATH DE number 1830732

Cites work

• A set containing rectifiable arcs QC-locally but not QC-globally
• Ergodic theory on \(SL(n)\), diophantine approximations and anomalies in the lattice point problem
• scientific article; zbMATH DE number 1645815 (Why is no real title available?)
• scientific article; zbMATH DE number 3987367 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• scientific article; zbMATH DE number 3019347 (Why is no real title available?)
• scientific article; zbMATH DE number 3052220 (Why is no real title available?)
• On a problem of Danzer
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Unsolved problems in geometry

Cited in

(4)

• Around the Danzer problem and the construction of dense forests
• On problems of Danzer and Gowers and dynamics on the space of closed subsets of R^d
• Danzer's problem, effective constructions of dense forests and digital sequences
• A new construction of forests with low visibility

Describes a project that uses

Uses Software

• Algorithm 247
• rhalton

This page was built for publication: A Danzer set for axis parallel boxes

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