Macbeath region

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

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

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 (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:

$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 $\epsilon$ approximations, with respect to the Hausdorff distance, of convex shapes within a factor of $O(\log ^{\frac {d+1}{2}}({\frac {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 \lambda <1$ then:

$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 $M_{K}^{\lambda }(x)$ is centrally symmetric around x.
• Macbeath regions are convex sets.
• If $x,y\in K$ and $M^{\frac {1}{2}}(x)\cap M^{\frac {1}{2}}(y)\neq \emptyset$ then $M^{1}(y)\subset M^{5}(x)$. 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 ${\frac {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 ${\frac {1}{6d}}$ then $C\subset M^{3d}(x)$, where x is the centroid of the base of the cap.
• Given a convex K and some constant $\lambda >0$, then for any point x in a cap C of K we know $M^{\lambda }(x)\cap K\subset C^{1+\lambda }$. In particular when $\lambda \leq 1$, we get $M^{\lambda }(x)\subset C^{1+\lambda }$.
• Given a convex body K, and a cap C of K, if x is in K and $C\cap M'(x)\neq \emptyset$ 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({\frac {1}{\epsilon ^{\frac {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 $\lambda$ depending on d we have:
  • Each $C_{i}$ has width $\beta \epsilon$, and $R_{i}\subset C_{i}\subset R_{i}^{\lambda }$
  • If C is any cap of width $\epsilon$ there must exist an i so that $R_{i}\subset C$ and $C_{i}^{\frac {1}{\beta ^{2}}}\subset C\subset C_{i}$

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.