Macbeath region explained

\R ^{d} . The idea was introduced by ^[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]}

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:

{M _{K}(x)=K} \cap ( 2 x - K) = x + ((K - x)\cap(x - K)) = \{k'\in K| \exists k \in K and k' - x = x - k \}

The scaled Macbeath region at x is defined as:

M ^{λ} _{K} (x) = x + λ ((K - x)\cap(x - K)) = \{( 1-λ )x +λ k'|k'\in K, \exists k\in K 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

\epsilon approximations, with respect to the Hausdorff distance, of convex shapes within a factor of O( log ^{(d +1)/(2)} ( (1)/(\epsilon) )) combinatorial complexity of the lower bound.

• Macbeath regions can be used to approximate balls in the Hilbert metric, e.g. given any convex K, containing an x and a

0 \leq λ < 1 then:^{[4] [6]} B _{H\left(x, (1)/(2)} ln ( 1+λ )\right)\subset M ^{λ} (x) \subset B _{H\left(x, (1)/(2)} ln (1+λ)/(1-λ) \right)

• Dikin’s Method

Properties

• The

M ^{λ} _{K} (x) is centrally symmetric around x.

• Macbeath regions are convex sets.
• If

x,y \in K and M ^{(1)/(2)} (x) \cap M ^{(1)/(2)} (y) ≠ \empty then 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

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 K \cap H of our convex set has a width less than or equal to (r)/(2) , we get K \cap H \subset M ^{3d(x)} for x, the center of gravity of K in the bounding hyper-plane of H.

• Given a convex body

K \subset R ^{d} in canonical form, then any cap of K with width at most (1)/(6 d) then C \subset M ^{3d} (x) , where x is the centroid of the base of the cap.

• Given a convex K and some constant

λ > 0 , then for any point x in a cap C of K we know M ^{λ} (x) \cap K \subset C ^{1+λ} . In particular when λ \leq 1 , we get M ^{λ} (x) \subset C ^{1+λ} .

• Given a convex body K, and a cap C of K, if x is in K and

C \cap M'(x) ≠ \empty we get M'(x)\subset C ^{2} .

• Given a small

\epsilon> 0 and a convex K\subset R ^{d} in canonical form, there exists some collection of O\left( (1)/(\epsilon ^{(d -1)/(2)}) \right) centrally symmetric disjoint convex bodies R _{1,....,R} _{k} and caps C _{1,....,C} _{k} such that for some constant \beta and λ depending on d we have:

• • Each

C _{i} has width \beta\epsilon , and R _{i} \subset C _{i} \subset R ^{λ} _{i}

• • If C is any cap of width

\epsilon there must exist an i so that R _{i} \subset C and C ^{(1)/(\beta ^{2})} _{i} \subset C \subset C _{i}

Further reading

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

Notes and References

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