Misplaced Pages

Macbeath region

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Brief description on Macbeath Regions
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 R d {\displaystyle \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 ∩ ( 2 x − K ) = x + ( ( K − x ) ∩ ( x − K ) ) = { k ′ ∈ K | ∃ k ∈ K  and  k ′ − x = x − k } {\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:

M K λ ( x ) = x + λ ( ( K − x ) ∩ ( x − K ) ) = { ( 1 − λ ) x + λ k ′ | k ′ ∈ K , ∃ k ∈ K  and  k ′ − x = x − k } {\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 O ( log d + 1 2 ⁡ ( 1 ϵ ) ) {\displaystyle 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 ≤ λ < 1 {\displaystyle 0\leq \lambda <1} then:
B H ( x , 1 2 ln ⁡ ( 1 + λ ) ) ⊂ M λ ( x ) ⊂ B H ( x , 1 2 ln ⁡ 1 + λ 1 − λ ) {\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 M K λ ( x ) {\displaystyle M_{K}^{\lambda }(x)} is centrally symmetric around x.
  • Macbeath regions are convex sets.
  • If x , y ∈ K {\displaystyle x,y\in K} and M 1 2 ( x ) ∩ M 1 2 ( y ) ≠ ∅ {\displaystyle M^{\frac {1}{2}}(x)\cap M^{\frac {1}{2}}(y)\neq \emptyset } then M 1 ( y ) ⊂ M 5 ( x ) {\displaystyle 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 {\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 K ∩ H {\displaystyle K\cap H} of our convex set has a width less than or equal to r 2 {\displaystyle {\frac {r}{2}}} , we get K ∩ H ⊂ M 3 d ( x ) {\displaystyle 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 ⊂ R d {\displaystyle K\subset R^{d}} in canonical form, then any cap of K with width at most 1 6 d {\displaystyle {\frac {1}{6d}}} then C ⊂ M 3 d ( x ) {\displaystyle C\subset M^{3d}(x)} , where x is the centroid of the base of the cap.
  • Given a convex K and some constant λ > 0 {\displaystyle \lambda >0} , then for any point x in a cap C of K we know M λ ( x ) ∩ K ⊂ C 1 + λ {\displaystyle M^{\lambda }(x)\cap K\subset C^{1+\lambda }} . In particular when λ ≤ 1 {\displaystyle \lambda \leq 1} , we get M λ ( x ) ⊂ C 1 + λ {\displaystyle 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 ∩ M ′ ( x ) ≠ ∅ {\displaystyle C\cap M'(x)\neq \emptyset } we get M ′ ( x ) ⊂ C 2 {\displaystyle M'(x)\subset C^{2}} .
  • Given a small ϵ > 0 {\displaystyle \epsilon >0} and a convex K ⊂ R d {\displaystyle K\subset R^{d}} in canonical form, there exists some collection of O ( 1 ϵ d − 1 2 ) {\displaystyle O\left({\frac {1}{\epsilon ^{\frac {d-1}{2}}}}\right)} centrally symmetric disjoint convex bodies R 1 , . . . . , R k {\displaystyle R_{1},....,R_{k}} and caps C 1 , . . . . , C k {\displaystyle C_{1},....,C_{k}} such that for some constant β {\displaystyle \beta } and λ {\displaystyle \lambda } depending on d we have:
    • Each C i {\displaystyle C_{i}} has width β ϵ {\displaystyle \beta \epsilon } , and R i ⊂ C i ⊂ R i λ {\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 R i ⊂ C {\displaystyle R_{i}\subset C} and C i 1 β 2 ⊂ C ⊂ C i {\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

Categories: