Макбет регион

Область Макбита вокруг точки x в выпуклом теле K и масштабированная область Макбита вокруг точки x в выпуклом теле K

В математике область Макбита — это явно определенная область в выпуклом анализе на ограниченном выпуклом подмножестве евклидова d -мерного пространства. $\mathbb {R} ^{d}$. Идею предложил Александр Макбит ( 1952 ). и дублирован Г. Эвальдом, Д. Г. Ларманом и К. А. Роджерсом в 1970 году. Области Макбита использовались для решения некоторых сложных задач при изучении границ выпуклых тел. В последнее время они стали использоваться при изучении выпуклых приближений и других аспектов вычислительной геометрии .

Определение

Пусть K — ограниченное выпуклое множество в евклидовом пространстве . Учитывая точку x и масштабатор λ, область Макбита вокруг точки x в масштабе λ равна:

${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\}$

Масштабированная область Макбита в точке x определяется как:

$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\}$

Можно увидеть, что это пересечение K с отражением K вокруг x, масштабируемым по λ.

Пример использования

• Регионы Макбита можно использовать для создания $\epsilon$ аппроксимации по отношению к расстоянию Хаусдорфа выпуклых форм с точностью до фактора $O(\log ^{\frac {d+1}{2}}({\frac {1}{\epsilon }}))$ комбинаторная сложность нижней оценки.
• Области Макбита можно использовать для аппроксимации шаров в метрике Гильберта , например, для любого выпуклого K , содержащего x и a. $0\leq \lambda <1$ затем:

$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)$

• Метод Дикина

Характеристики

• The $M_{K}^{\lambda }(x)$ центрально симметричен относительно x.
• Области Макбита представляют собой выпуклые множества .
• Если $x,y\in K$ и $M^{\frac {1}{2}}(x)\cap M^{\frac {1}{2}}(y)\neq \emptyset$ затем $M^{1}(y)\subset M^{5}(x)$. По сути, если две области Макбита пересекаются, вы можете масштабировать одну из них, чтобы вместить другую.
• Если некоторый выпуклый K в $R^{d}$ содержащий как шар радиуса r, так и полупространство H , полупространство которого не пересекается с шаром, и шапку $K\cap H$ нашего выпуклого множества имеет ширину, меньшую или равную ${\frac {r}{2}}$, мы получаем $K\cap H\subset M^{3d(x)}$ для x центр тяжести K в ограничивающей гиперплоскости H. —
• Учитывая выпуклое тело $K\subset R^{d}$ в канонической форме, то любая шапочка K шириной не более ${\frac {1}{6d}}$ затем $C\subset M^{3d}(x)$, где x — центр тяжести основания колпачка.
• Учитывая выпуклый K и некоторую константу $\lambda >0$, то для любой точки x в шапке C группы K мы знаем $M^{\lambda }(x)\cap K\subset C^{1+\lambda }$. В частности, когда $\lambda \leq 1$, мы получаем $M^{\lambda }(x)\subset C^{1+\lambda }$.
• Учитывая выпуклое тело K и шапку C тела K , если x находится в K и $C\cap M'(x)\neq \emptyset$ мы получаем $M'(x)\subset C^{2}$.
• Учитывая небольшой $\epsilon >0$ и выпуклый $K\subset R^{d}$ в канонической форме существует некоторая совокупность $O\left({\frac {1}{\epsilon ^{\frac {d-1}{2}}}}\right)$ центрально-симметричные непересекающиеся выпуклые тела $R_{1},....,R_{k}$ и шапки $C_{1},....,C_{k}$ такой, что для некоторой постоянной $\beta$ и $\lambda$ в зависимости от d имеем:
  • Каждый $C_{i}$ имеет ширину $\beta \epsilon$, и $R_{i}\subset C_{i}\subset R_{i}^{\lambda }$
  • Если C — любая крышка шириной $\epsilon$ должно существовать i , чтобы $R_{i}\subset C$ и $C_{i}^{\frac {1}{\beta ^{2}}}\subset C\subset C_{i}$

Дальнейшее чтение

• Дутта, Кунал; Гош, Ариджит; Жарту, Брюно; Мустафа, Набиль (2019). «Мелкие упаковки, полуалгебраические системы множеств, области Макбита и полиномиальное разбиение» . Дискретная и вычислительная геометрия . 61 (4): 756–777. дои : 10.1007/s00454-019-00075-0 . S2CID   127559205 .