Macbeath region

In mathematics, a Macbeath region is an explicitly defined region in convex analysis on a bounded convex subset of d-dimensional Euclidean space ${\displaystyle \mathbb {R} ^{d}}$. The idea was introduced by Alexander Macbeath (1952)^[1] and dubbed by G. Ewald, D. G. Larman and C. A. Rogers in 1970.^[2] Macbeath regions have been used to solve certain complex problems in the study of the boundaries of convex bodies.^[3] Recently they have been used in the study of convex approximations and other aspects of computational geometry.^[4][5]

The Macbeath region around a point x in a convex body K and the scaled Macbeath region around a point x in a convex body K

Definition

Let K be a bounded convex set in a Euclidean space. Given a point x and a scaler λ the λ-scaled the Macbeath region around a point x is:

${\displaystyle {M_{K}}(x)=K\cap (2x-K)=x+((K-x)\cap (x-K))=\{k'\in K|\exists k\in K{\text{ and }}k'-x=x-k\}}$

The scaled Macbeath region at x is defined as:

${\displaystyle M_{K}^{\lambda }(x)=x+\lambda ((K-x)\cap (x-K))=\{(1-\lambda )x+\lambda k'|k'\in K,\exists k\in K{\text{ and }}k'-x=x-k\}}$

This can be seen to be the intersection of K with the reflection of K around x scaled by λ.

Example uses

• Macbeath regions can be used to create ${\displaystyle \epsilon }$ approximations, with respect to the Hausdorff distance, of convex shapes within a factor of ${\displaystyle O(\log ^{\frac {d+1}{2}}({\frac {1}{\epsilon }}))}$ combinatorial complexity of the lower bound.^[5]
• Macbeath regions can be used to approximate balls in the Hilbert metric, e.g. given any convex K, containing an x and a ${\displaystyle 0\leq \lambda <1}$ then:^[4][6]

${\displaystyle B_{H}\left(x,{\frac {1}{2}}\ln(1+\lambda )\right)\subset M^{\lambda }(x)\subset B_{H}\left(x,{\frac {1}{2}}\ln {\frac {1+\lambda }{1-\lambda }}\right)}$

• Dikin’s Method

Properties

• The ${\displaystyle M_{K}^{\lambda }(x)}$ is centrally symmetric around x.
• Macbeath regions are convex sets.
• If ${\displaystyle x,y\in K}$ and ${\displaystyle M^{\frac {1}{2}}(x)\cap M^{\frac {1}{2}}(y)\neq \emptyset }$ then ${\displaystyle M^{1}(y)\subset M^{5}(x)}$.^[3][4] Essentially if two Macbeath regions intersect, you can scale one of them up to contain the other.
• If some convex K in ${\displaystyle R^{d}}$ containing both a ball of radius r and a half-space H, with the half-space disjoint from the ball, and the cap ${\displaystyle K\cap H}$ of our convex set has a width less than or equal to ${\displaystyle {\frac {r}{2}}}$, we get ${\displaystyle K\cap H\subset M^{3d(x)}}$ for x, the center of gravity of K in the bounding hyper-plane of H.^[3]
• Given a convex body ${\displaystyle K\subset R^{d}}$ in canonical form, then any cap of K with width at most ${\displaystyle {\frac {1}{6d}}}$ then ${\displaystyle C\subset M^{3d}(x)}$, where x is the centroid of the base of the cap.^[5]
• Given a convex K and some constant ${\displaystyle \lambda >0}$, then for any point x in a cap C of K we know ${\displaystyle M^{\lambda }(x)\cap K\subset C^{1+\lambda }}$. In particular when ${\displaystyle \lambda \leq 1}$, we get ${\displaystyle M^{\lambda }(x)\subset C^{1+\lambda }}$.^[5]
• Given a convex body K, and a cap C of K, if x is in K and ${\displaystyle C\cap M'(x)\neq \emptyset }$ we get ${\displaystyle M'(x)\subset C^{2}}$.^[5]
• Given a small ${\displaystyle \epsilon >0}$ and a convex ${\displaystyle K\subset R^{d}}$ in canonical form, there exists some collection of ${\displaystyle O\left({\frac {1}{\epsilon ^{\frac {d-1}{2}}}}\right)}$ centrally symmetric disjoint convex bodies ${\displaystyle R_{1},....,R_{k}}$ and caps ${\displaystyle C_{1},....,C_{k}}$ such that for some constant ${\displaystyle \beta }$ and ${\displaystyle \lambda }$ depending on d we have:^[5]
  • Each ${\displaystyle C_{i}}$ has width ${\displaystyle \beta \epsilon }$, and ${\displaystyle R_{i}\subset C_{i}\subset R_{i}^{\lambda }}$
  • If C is any cap of width ${\displaystyle \epsilon }$ there must exist an i so that ${\displaystyle R_{i}\subset C}$ and ${\displaystyle C_{i}^{\frac {1}{\beta ^{2}}}\subset C\subset C_{i}}$

References

1. Macbeath, A. M. (September 1952). "A Theorem on Non-Homogeneous Lattices". The Annals of Mathematics. 56 (2): 269–293. doi:10.2307/1969800. JSTOR 1969800.
2. Ewald, G.; Larman, D. G.; Rogers, C. A. (June 1970). "The directions of the line segments and of the r-dimensional balls on the boundary of a convex body in Euclidean space". Mathematika. 17 (1): 1–20. doi:10.1112/S0025579300002655.
3. Bárány, Imre (June 8, 2001). "The techhnique of M-regions and cap-coverings: a survey". Rendiconti di Palermo. 65: 21–38.
4. Abdelkader, Ahmed; Mount, David M. (2018). "Economical Delone Sets for Approximating Convex Bodies". 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). 101: 4:1–4:12. doi:10.4230/LIPIcs.SWAT.2018.4.
5. Arya, Sunil; da Fonseca, Guilherme D.; Mount, David M. (December 2017). "On the Combinatorial Complexity of Approximating Polytopes". Discrete & Computational Geometry. 58 (4): 849–870. arXiv:1604.01175. doi:10.1007/s00454-016-9856-5. S2CID 1841737.
6. Vernicos, Constantin; Walsh, Cormac (2021). "Flag-approximability of convex bodies and volume growth of Hilbert geometries". Annales Scientifiques de l'École Normale Supérieure. 54 (5): 1297–1314. arXiv:1809.09471. doi:10.24033/asens.2482. S2CID 53689683.

Further reading

• Dutta, Kunal; Ghosh, Arijit; Jartoux, Bruno; Mustafa, Nabil (2019). "Shallow Packings, Semialgebraic Set Systems, Macbeath Regions, and Polynomial Partitioning". Discrete & Computational Geometry. 61 (4): 756–777. doi:10.1007/s00454-019-00075-0. S2CID 127559205.