マクビース地域

数学において、マクビース領域は、 d次元ユークリッド空間の有界凸部分集合上の凸解析において明示的に定義された領域である。このアイデアは、アレクサンダー・マクビース （1952）^[1]によって導入され、1970年にG.エワルド、DGラーマン、CAロジャースによって名付けられた。^[2]マクビース領域は、凸体の境界の研究における特定の複雑な問題を解決するために使用されてきた。^{[3]最近では、凸近似や}計算幾何学の他の側面の研究に使用されている。^{[4] [5]} ${\displaystyle \mathbb {R} ^{d}}$

K をユークリッド空間内の有界凸集合とする。点xとスケーラー λ が与えられたとき、点x の周りの λ スケールのマクビース領域は次のようになる。

${\displaystyle {M_{K}}(x)=K\cap (2x-K)=x+((Kx)\cap (xK))=\{k'\in K|\exists k\in K{\text{ かつ }}k'-x=xk\}}$

xにおけるスケールされたマクビース領域は次のように定義されます。

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

これは、λ でスケールされたxの周りのKの反射とKの交差であると見ることができます。

• マクビース領域は、ハウスドルフ距離に関して、下限の組み合わせ複雑度の係数内で凸形状の近似を作成するために使用できます。 ^[5]${\displaystyle \epsilon }$${\displaystyle O(\log ^{\frac {d+1}{2}}({\frac {1}{\epsilon }}))}$
• マクビース領域はヒルベルト計量における球を近似するのに使用できる。例えば、任意の凸包Kが与えられ、そこにxとaが含まれている場合、次のようになる。^{[4] [6]}${\displaystyle 0\leq \lambda <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)}$

• ディキン法

• はx を中心に対称です。${\displaystyle M_{K}^{\lambda }(x)}$
• マクビース領域は凸集合である。
• であれば、 となります。^{[3] [4]}基本的に、2つのマクビース領域が交差する場合、一方を拡大してもう一方を含めることができます。${\displaystyle x,y\in K}$${\displaystyle M^{\frac {1}{2}}(x)\cap M^{\frac {1}{2}}(y)\neq \emptyset }$${\displaystyle M^{1}(y)\subset M^{5}(x)}$
• 半径 r の球と半空間H の両方を含む凸集合K があり、半空間は球と交わっておらず、凸集合のキャップの幅が かそれ以下であれば、 xに対して、 Hの境界超平面における K の重心が得られます。^[3]${\displaystyle R^{d}}$${\displaystyle K\cap H}$${\displaystyle {\frac {r}{2}}}$${\displaystyle K\cap H\subset M^{3d(x)}}$
• 標準形の凸体が与えられたとき、 Kの任意のキャップの幅は最大で となり、ここでxはキャップの底の重心である。^[5]${\displaystyle K\subset R^{d}}$${\displaystyle {\frac {1}{6d}}}$${\displaystyle C\subset M^{3d}(x)}$
• 凸包Kと定数が与えられたとき、 KのキャップC内の任意の点xに対して が分かります。特に のとき、 が得られます。^[5]${\displaystyle \lambda >0}$${\displaystyle M^{\lambda }(x)\cap K\subset C^{1+\lambda }}$${\displaystyle \lambda \leq 1}$${\displaystyle M^{\lambda }(x)\subset C^{1+\lambda }}$
• 凸体KとKのキャップCが与えられ、xがKに属している場合は、 次を得る。^[5]${\displaystyle C\cap M'(x)\neq \emptyset }$${\displaystyle M'(x)\subset C^{2}}$
• 小さな凸包と標準形の凸包が与えられたとき、中心対称な互いに素な凸体と凸包の集合が存在し、ある定数に対して、dに依存して次式が成り立つ。^[5]${\displaystyle \epsilon >0}$${\displaystyle K\subset R^{d}}$${\displaystyle O\left({\frac {1}{\epsilon ^{\frac {d-1}{2}}}}\right)}$${\displaystyle R_{1},....,R_{k}}$${\displaystyle C_{1},....,C_{k}}$${\displaystyle \beta}$${\displaystyle \lambda}$
  • それぞれ幅は で、${\displaystyle C_{i}}$${\displaystyle \beta \epsilon }$${\displaystyle R_{i}\subset C_{i}\subset R_{i}^{\lambda}}$
  • Cが任意の幅の上限である場合、iが存在し、${\displaystyle \epsilon }$${\displaystyle R_{i}\subset C}$${\displaystyle C_{i}^{\frac {1}{\beta ^{2}}}\subset C\subset C_{i}}$

• Dutta, Kunal; Ghosh, Arijit; Jartoux, Bruno; Mustafa, Nabil (2019). 「浅いパッキング、半代数集合システム、マクビース領域、および多項式分割」。離散幾何学と計算幾何学。61 (4): 756–777. doi : 10.1007/s00454-019-00075-0. S2CID  127559205。