A Danzer set for axis parallel boxes
type: Item
instance of: scholarly article
title: A Danzer set for axis parallel boxes
zbMATH Open document ID: 1339.54028
author: David Simmons
author: Yaar Solomon
published in: Proceedings of the American Mathematical Society
publication date: 2016-03-29T00:00:00Z
full work available at URL: https://arxiv.org/abs/1409.0926
full work available at URL: doc.pdf
Mathematics Subject Classification ID: 54H20
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 68R01
zbMATH DE Number: 6560798
zbMATH Keywords: Danzer set
zbMATH Keywords: volume
zbMATH Keywords: growth rate
zbMATH Keywords: aligned boxes
zbMATH Keywords: dense forest
zbMATH Keywords: admissible lattice
zbMATH Keywords: codiameter
zbMATH Keywords: ring of integers
zbMATH Keywords: Galois embeddings
describes a project that uses: Algorithm 247
describes a project that uses: rhalton
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W2963330066
arXiv ID: 1409.0926
cites work: Q3503433
cites work: A set containing rectifiable arcs QC-locally but not QC-globally
cites work: On a problem of Danzer
cites work: Q5759854
cites work: Unsolved problems in geometry
cites work: Q2737646
cites work: Q3751649
cites work: Q5791470
cites work: Q4530626
cites work: Ergodic theory on \(SL(n)\), diophantine approximations and anomalies in the lattice point problem
DOI: 10.1090/PROC/12911
Recommended article: Dense forests and Danzer sets
Recommended article: Around the Danzer problem and the construction of dense forests
Recommended article: A note about weak \(\epsilon \)-nets for axis-parallel boxes in \(d\)-space
Recommended article: Efficient construction of a small hitting set for combinatorial rectangles in high dimension
Recommended article: A Dynamical System Using the Voronoï Tessellation
Recommended article: Danzer's problem, effective constructions of dense forests and digital sequences
Recommended article: On the number of unit-area triangles spanned by convex grids in the plane
Recommended article: Towards Faster Linear-Sized Nets for Axis-Aligned Boxes in the Plane
Recommended article: Dispersion of digital \((0,m,2)\)-nets
Recommended article: Q4778553
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.
reviewed by: Antonio Linero Bas
description: scientific article; zbMATH DE number 6560798