Случайный многогранник

В математике — случайный многогранник это структура, обычно используемая в выпуклом анализе и анализе линейных программ в d -мерном евклидовом пространстве. $\mathbb {R} ^{d}$ . ^{[ 1 ]}^{[ 2 ]} В зависимости от используемой конструкции и определения случайные многогранники могут различаться.

Определение

Существует несколько неэквивалентных определений случайного многогранника. Для следующих определений. Пусть K — ограниченное выпуклое множество в евклидовом пространстве :

Выпуклая оболочка случайных точек, выбранных относительно равномерного распределения внутри K. ^{[ 2 ]}
Непустое пересечение полупространств в $\mathbb {R} ^{d}$ $\mathbb {R} ^{d}$ . ^{[ 1 ]}
- Использовалась следующая параметризация: $r:(\mathbb {R} ^{d}\times \{0,1\})^{m}\rightarrow {\text{Polytopes}}\in \mathbb {R} ^{d}$ такой, что $r((p_{1},0),(p_{2},1),(p_{3},1)...(p_{m},i_{m}))=\{x\in \mathbb {R} ^{n}:|{\frac {p_{j}}{||p_{j}||}}\cdot x\leq ||p_{j}||{\text{ if }}i_{j}=1,{\frac {p_{j}}{||p_{j}||}}\cdot x\geq ||p_{j}||{\text{ if }}i_{j}=0\}$ (Примечание: эти многогранники могут быть пустыми). ^{[ 1 ]}

Определение свойств 1

Позволять $\mathrm {K}$ — множество выпуклых тел в $\mathbb {R} ^{d}$ . Предполагать $K\in \mathrm {K}$ и рассмотрим набор равномерно распределенных точек $x_{1},...,x_{n}$ в $K$ . Выпуклая оболочка этих точек $K_{n}$ , называется случайным многогранником, вписанным в $K$ . $K_{n}=[x_{1},...,x_{n}]$ где набор $[S]$ обозначает выпуклую оболочку множества. ^{[ 2 ]} Мы определяем $E(k,n)$ быть ожидаемым объемом $K-K_{n}$ . Для достаточно большого $n$ и учитывая $K\in \mathbb {R} ^{n}$ .

том $K({\frac {1}{n}})\ll E(K,n)\ll$ $K({\frac {1}{n}})\ll E(K,n)\ll$ том $K({\frac {1}{n}})$ $K({\frac {1}{n}})$ ^{[ 2 ]}
- Примечание. Можно определить объем мокрой части, чтобы получить порядок величины $E(K,n)$ , вместо того, чтобы определять $E(K,n)$ . ^{[ 3 ]}
Для единичного шара $B^{d}\in \mathbb {R} ^{d}$ , мокрая часть $B^{d}(v\leq t)$ это кольцевое пространство ${\frac {B^{d}}{(1-h)B^{d}}}$ где h имеет порядок $t^{\frac {2}{d+1}}$ : $E(B^{d},n)\approx$ том $B^{d}({\frac {1}{n}})\approx n^{\frac {-2}{d+1}}$ ^{[ 2 ]}

Учитывая, что у нас есть $V=V(x_{1},...,x_{d})$ — объем меньшей крышки, отрезанной от $K$ автор: aff $(x_{1},...,x_{d})$ , и $F=[x_{1},...,x_{d}]$ является фасетом тогда и только тогда, когда $x_{d+1},...,x_{n}$ все на одной стороне $\{x_{1},...,x_{d}\}$ .

$E_{\phi }(K_{n})={{n} \choose {d}}\int _{K}...\int _{K}[(1-V)^{n-d}+V^{n-d}]\phi (F)dx_{1}...dx_{d}$ $E_{\phi }(K_{n})={{n} \choose {d}}\int _{K}...\int _{K}[(1-V)^{nd} +V^{nd}]\phi (F)dx_{1}...dx_{d}$ . ^{[ 2 ]}
- Примечание: Если $\phi =f_{d-1}$ (функция, возвращающая количество d-1 размерных граней), тогда $\phi (F)=1$ и формула может быть вычислена для гладких выпуклых множеств и для многоугольников на плоскости.

Определение свойств 2

Предположим, нам дано многомерное распределение вероятностей на $(\mathbb {R} ^{d}\times \{0,1\})^{m}=(p_{1}\times i_{1},\dots ,p_{m}\times i_{m})^{m}$ то есть

Абсолютно непрерывно включен $(p_{1},\dots ,p_{d})$ относительно меры Лебега .
Генерирует либо 0, либо 1 для $i$ с вероятностью ${\frac {1}{2}}$ каждый.
Присваивает меру 0 множеству элементов в $(\mathbb {R} ^{d}\times \{0,1\})^{m}$ соответствующие пустым многогранникам.

Учитывая это распределение и наши предположения, выполняются следующие свойства:

Выведена формула для ожидаемого количества $k$ размерные грани на многограннике в $\mathbb {R} ^{d}$ с $m$ ограничения: $E_{k}(m)=2^{d-k}\sum _{i=d-k}^{d}{{i} \choose {d-k}}{{m} \choose {i}}/\sum _{i=0}^{d}{{m} \choose {i}}$ . (Примечание: $\lim _{m\to \infty }E_{k}(m)={{d} \choose {d-k}}2^{d-k}$ где $m>d$ ). Верхняя граница или худший случай числа вершин с $m$ ограничений гораздо больше: $V_{max}={m-[{\frac {1}{2}}(d+1)] \choose m-d}+{m-[{\frac {1}{2}}(d+2)] \choose m-d}$ . ^{[ 1 ]}
Вероятность того, что новое ограничение окажется избыточным, равна: $\pi _{m}=1-{\frac {2\sum _{i=0}^{d-1}{{m-1} \choose i}}{\sum _{i=0}^{d}{m \choose i}}}$ . (Примечание: $\lim _{m\to \infty }{\pi _{m}}=1$ , и по мере добавления новых ограничений вероятность того, что новое ограничение окажется избыточным, приближается к 100%). ^{[ 1 ]}
Ожидаемое количество неизбыточных ограничений: $C_{d}(m)={\frac {2m\sum _{i=0}^{d-1}{{m-1} \choose i}}{\sum _{i=0}^{d}{{m} \choose i}}}$ . (Примечание: $\lim _{m\to \infty }C_{d}(m)=2d$ ). ^{[ 1 ]}

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

Минимальные ограничения
Макбет регионы
Приближения (приближения выпуклых тел см. свойства определения 1)
Теорема о покрытии экономического лимита (см. Связь свойств определения 1 с плавающими телами)

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и ^ж Мэй, Джеррольд Х.; Смит, Роберт Л. (декабрь 1982 г.). «Случайные многогранники: их определение, генерация и агрегатные свойства». Математическое программирование . 24 (1): 39–54. дои : 10.1007/BF01585093 . hdl : 2027.42/47911 . S2CID 17838156 .
^ Jump up to: ^а ^б ^с ^д ^и ^ж Бэддели, Адриан; Барань, Имре ; Шнайдер, Рольф; Вейль, Вольфганг, ред. (2007), «Случайные многогранники, выпуклые тела и приближение» , Стохастическая геометрия: лекции, прочитанные на Летней школе CIME, проходившей в Мартина Франка, Италия, 13–18 сентября 2004 г. , Конспекты лекций по математике, том. 1892, Берлин, Гейдельберг: Springer, стр. 77–118, CiteSeerX 10.1.1.641.3187 , doi : 10.1007/978-3-540-38175-4_2 , ISBN 978-3-540-38175-4 , получено 1 апреля 2022 г.
^ Барань, И .; Ларман, генеральный директор (декабрь 1988 г.). «Выпуклые тела, экономические покрытия, случайные многогранники». Математика . 35 (2): 274–291. дои : 10.1112/S0025579300015266 .

[:1-1] Jump up to: ^а ^б ^с ^д ^и ^ж Мэй, Джеррольд Х.; Смит, Роберт Л. (декабрь 1982 г.). «Случайные многогранники: их определение, генерация и агрегатные свойства». Математическое программирование . 24 (1): 39–54. дои : 10.1007/BF01585093 . hdl : 2027.42/47911 . S2CID 17838156 .

[:0-2] Jump up to: ^а ^б ^с ^д ^и ^ж Бэддели, Адриан; Барань, Имре ; Шнайдер, Рольф; Вейль, Вольфганг, ред. (2007), «Случайные многогранники, выпуклые тела и приближение» , Стохастическая геометрия: лекции, прочитанные на Летней школе CIME, проходившей в Мартина Франка, Италия, 13–18 сентября 2004 г. , Конспекты лекций по математике, том. 1892, Берлин, Гейдельберг: Springer, стр. 77–118, CiteSeerX 10.1.1.641.3187 , doi : 10.1007/978-3-540-38175-4_2 , ISBN 978-3-540-38175-4 , получено 1 апреля 2022 г.

[3] Барань, И .; Ларман, генеральный директор (декабрь 1988 г.). «Выпуклые тела, экономические покрытия, случайные многогранники». Математика . 35 (2): 274–291. дои : 10.1112/S0025579300015266 .

[ 1 ]

[ 2 ]

[ 3 ]