418
правок
Изменения
Нет описания правки
{{Лемма
|id=lemma1
|about=1
|statement=
Пусть <tex>P</tex> — выпуклый многогранник с <tex>n</tex> вершинами. Тогда число его рёбер не превосходит <tex>3n - 6</tex>, а число его граней — <tex>2n - 4</tex>.
[[Файл:3dconvexhullprojection.png|300px|thumb|right|Верхняя грань куба спроецировалась на внешнюю грань графа]]
«Спроецируем» многогранник на плоскость, как на картинке. Получили планарный граф, по формуле Эйлера имеем <tex>n - n_e + n_f = 2</tex>, где <tex>n_e</tex> — число рёбер, <tex>n_f</tex> — число граней. Каждая грань нашего графа имеет по меньшей мере 3 ребра, каждое ребро инцидентно двум граням, поэтому имеем <tex>2 n_e \geqslant 3 n_f</tex>. Тогда получаем <tex>n_f \leqslant 2n - 4</tex>, и, подставив это в формулу Эйлера, <tex>n_e \leqslant 3n - 6</tex>.
}}
{{Лемма
|id=lemma2
|about=2
|statement=
Ожидаемое число граней, создаваемое нашим алгоритмом, не превосходит <tex>6n - 20</tex>.
|proof=
Рассмотрим добавление точки <tex>p_r</tex>. Все грани, добавленные на этом шаге алгоритма, инцидентны этой точке, равно как и добавленные рёбра. Обозначим число инцидентных точке <tex>p_i</tex> рёбер (степень вершины; оно же число инцидентных точек) в выпуклой оболочке <tex>r</tex> точек как <tex>k_{i, r}</tex>.
По [[#lemma1|лемме 1]] у многогранника с <tex>r</tex> веришнами не больше <tex>3r - 6</tex> рёбер. Значит, сумма степеней вершин многогранника не больше <tex>6r - 12</tex>. Значит, средняя степень вершины равна <tex>6 - 12/r</tex>. Точки берутся в случайном порядке, поэтому можно считать, что ожидаемая степень вершины <tex>p_r</tex> равна <tex>6 - 12/r</tex>. Это рассуждение верно только для <tex>r > 4</tex>, так как первые четыре точки фиксированы, их суммарная степень равна <tex>12</tex>. Посчитаем математическое ожидание <tex>k_r</tex>:
<tex>E(k_{r, r}) = \frac{1}{r - 4} \sum_{i = 5}^{r} k_{i, r} \leqslant \frac{1}{r - 4} ( \sum_{i = 1}^{r} k_{i, r} - 12 ) \leqslant \frac{6r - 12 - 12}{r - 4} = 6</tex>.
Ожидаемое число граней — это число граней в начальном тетраэдре (4 — ваш К.О.) плюс ожидаемое общее число созданных граней при добавлении точек. Поэтому искомое число равно <tex>4 + \sum_{r = 5}^{n} E(k_{r, r}) \leqslant 4 + 6(n - 4) = 6n - 20</tex>.
}}
