Выпуклая оболочка в n-мерном пространстве — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Время работы)
(не показано 8 промежуточных версий 2 участников)
Строка 1: Строка 1:
{{notready}}, и я помню про дедлайн :(
+
{{ptready}}
Рассмотрим трёхмерный случай. <tex>n</tex>-мерный случай сводится к трёхмерному.
+
Рассмотрим трёхмерный случай. <tex>n</tex>-мерный сводится к трёхмерному.
  
== Алгоритм ==
+
==Суть алгоритма==
 
Выберем любые две точки <tex>p_1</tex> и <tex>p_2</tex>. Далее из оставшихся выберем точку <tex>p_3</tex>, которая не лежит на прямой, образованной точками <tex>p_1</tex> и <tex>p_2</tex>. После этого выберем точку <tex>p_4</tex>, которая не лежит на плоскости, образованной точками <tex>p_1, p_2</tex> и <tex>p_3</tex>. Если этого сделать не получилось, то запустим алгоритм для поиска выпуклой оболочки на плоскости.
 
Выберем любые две точки <tex>p_1</tex> и <tex>p_2</tex>. Далее из оставшихся выберем точку <tex>p_3</tex>, которая не лежит на прямой, образованной точками <tex>p_1</tex> и <tex>p_2</tex>. После этого выберем точку <tex>p_4</tex>, которая не лежит на плоскости, образованной точками <tex>p_1, p_2</tex> и <tex>p_3</tex>. Если этого сделать не получилось, то запустим алгоритм для поиска выпуклой оболочки на плоскости.
  
Так мы получили тетраэдр <tex>p_1 p_2 p_3 p_4</tex>. Сделаем random shuffle оставшихся точек <tex>p_5, ..., p_n</tex>.
+
Так мы получили тетраэдр <tex>p_1 p_2 p_3 p_4</tex>, который является выпуклой оболочкой этих четырёх точек. Сделаем random shuffle оставшихся точек <tex>p_5, ..., p_n</tex> и будем добавлять их по одной в выпуклую оболочку. Если <tex>p_i</tex> внутри или на границах выпуклой оболочки, то выпуклая оболочка не меняется на этом шаге. Иначе из имеющейся выпуклой оболочки надо удалить все видимые из данной точки грани и добавить новые — из точки до каждого ребра, образующего horizon (см. картинки; на них белые грани видны из точки <tex>p_r</tex>). После этого нужно смержить соседние грани, которые получились компланарными.
 +
 
 +
[[Файл:3dconvexhullhorizon.png]] [[Файл:3dconvexhulladd.png]]
 +
 
 +
==Детали реализации==
 +
Будем хранить выпуклую оболочку в виде DCEL.
 +
 
 +
Для выяснения, какие грани видны из точки, будем хранить двудольный граф <tex>G</tex>, называемый conflict graph, в одной доле которого будут точки, которые ещё не добавлены в выпуклую оболочку, а в другой — имеющиеся на данный момент грани выпуклой оболочки. Ребро между точкой <tex>p</tex> и гранью <tex>f</tex> в этом графе означает, что из <tex>p</tex> видна <tex>f</tex>, то есть они находятся в конфликте (in conflict): они не могут сосуществовать в выпуклой оболочке.
 +
 
 +
Инициализация графа для тетраэдра тривиальна: для каждой точки определяем, какие грани видны из неё. Далее на каждом шаге после добавления точки <tex>p_r</tex> удалим из графа соответствующие удаляемым из выпуклой оболочки граням вершины и инцидентные им рёбра: просто удаляем все достижимые из <tex>p_r</tex> вершины. Также удалим вершину, соответствующую <tex>p_r</tex>. Далее добавляем новые грани выпуклой оболочки. Необходимо найти их конфликты. Сами грани представляют из себя треугольники, если, конечно, они не были смержены с уже имеющимися гранями. Во втором случае новая грань находится в конфликте с теми же точками, что и старая грань, т.к. смерженные грани компланарны.
 +
 
 +
[[Файл:3dconvexhullconflictlist.png|200px|thumb|left]]
 +
Перейдём к первому случаю. Пусть мы добавили точку <tex>p_r</tex> и рассматриваем грань <tex>f</tex>. <tex>e</tex> — ребро, принадлежащее horizon, <tex>f_1, f_2</tex> — грани, пересечение которых образовывало <tex>e</tex> в старой оболочке. Пусть <tex>p_t</tex> — ещё не добавленная точка, из которой видно <tex>f</tex>, тогда из неё видно и ребро <tex>e</tex>, причём как в новой, так и в старой выпуклой оболочке (так как новая включает в себя старую). Но это возможно, только если из <tex>p_t</tex> видно <tex>f_1</tex> или <tex>f_2</tex>. Значит, точки, с которыми у <tex>f</tex> есть конфликт — это только какие-то из точек, у которых есть конфликт у <tex>f_1</tex> и <tex>f_2</tex>.
 +
 
 +
==Время работы==
 +
{{Лемма
 +
|id=lemma1
 +
|about=1
 +
|statement=
 +
Пусть <tex>P</tex> — выпуклый многогранник с <tex>n</tex> вершинами. Тогда число его рёбер не превосходит <tex>3n - 6</tex>, а число его граней — <tex>2n - 4</tex>.
 +
|proof=
 +
[[Файл: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> (если не удаётся это понять, можно представить двудольный граф, где слева грани, а справа рёбра. Из каждого ребра исходит ровно 2 вершины, а в каждую грань входит хотя бы 3). Тогда получаем <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>.
 +
}}
 +
 
 +
{{Теорема
 +
|statement=
 +
Время работы алгоритма — <tex>O(n \log n)</tex>.
 +
|proof=
 +
Шаги перед добавлением точек можно сделать за <tex>O(n \log n)</tex>. Очередной шаг требует константного времени, если <tex>m_r</tex> — число конфликтных граней для добавляемой точки — равно нулю (то есть когда точка внутри или на границах имеющейся выпуклой оболочки). Иначе этот шаг требует <tex>O(m_r)</tex> времени плюс время на удаление видимых рёбер (удалить ребро можно не больше одного раза, поэтому можно считать, что этот шаг лишь изменит константу во времени создания новых рёбер) и изменение графа конфликтов.
 +
 
 +
Заметим, что <tex>m_r</tex> — число граней, удалённых на очередном шаге алгоритма, поэтому по [[#lemma2|лемме 2]] <tex>E(\sum_{r = 5}^{n} m_r) = O(n)</tex>.
 +
 
 +
При изменении графа конфликтов на шаге <tex>r</tex> требуется время, равное сумме числа конфликтных точек для смежных граней каждого ребра на horizon. Это меньше либо равно числу всех конфликтных точек для всех граней. Утверждается, что оно равно <tex>O(n \log n)</tex>, и это надо как-то доказать (в де Берге есть, надо разобраться и дополнить), и тогда теорема доказана.
 +
}}

Версия 22:58, 10 февраля 2015

Конспект написан не до конца, но основные вещи уже есть.

Рассмотрим трёхмерный случай. [math]n[/math]-мерный сводится к трёхмерному.

Суть алгоритма

Выберем любые две точки [math]p_1[/math] и [math]p_2[/math]. Далее из оставшихся выберем точку [math]p_3[/math], которая не лежит на прямой, образованной точками [math]p_1[/math] и [math]p_2[/math]. После этого выберем точку [math]p_4[/math], которая не лежит на плоскости, образованной точками [math]p_1, p_2[/math] и [math]p_3[/math]. Если этого сделать не получилось, то запустим алгоритм для поиска выпуклой оболочки на плоскости.

Так мы получили тетраэдр [math]p_1 p_2 p_3 p_4[/math], который является выпуклой оболочкой этих четырёх точек. Сделаем random shuffle оставшихся точек [math]p_5, ..., p_n[/math] и будем добавлять их по одной в выпуклую оболочку. Если [math]p_i[/math] внутри или на границах выпуклой оболочки, то выпуклая оболочка не меняется на этом шаге. Иначе из имеющейся выпуклой оболочки надо удалить все видимые из данной точки грани и добавить новые — из точки до каждого ребра, образующего horizon (см. картинки; на них белые грани видны из точки [math]p_r[/math]). После этого нужно смержить соседние грани, которые получились компланарными.

3dconvexhullhorizon.png 3dconvexhulladd.png

Детали реализации

Будем хранить выпуклую оболочку в виде DCEL.

Для выяснения, какие грани видны из точки, будем хранить двудольный граф [math]G[/math], называемый conflict graph, в одной доле которого будут точки, которые ещё не добавлены в выпуклую оболочку, а в другой — имеющиеся на данный момент грани выпуклой оболочки. Ребро между точкой [math]p[/math] и гранью [math]f[/math] в этом графе означает, что из [math]p[/math] видна [math]f[/math], то есть они находятся в конфликте (in conflict): они не могут сосуществовать в выпуклой оболочке.

Инициализация графа для тетраэдра тривиальна: для каждой точки определяем, какие грани видны из неё. Далее на каждом шаге после добавления точки [math]p_r[/math] удалим из графа соответствующие удаляемым из выпуклой оболочки граням вершины и инцидентные им рёбра: просто удаляем все достижимые из [math]p_r[/math] вершины. Также удалим вершину, соответствующую [math]p_r[/math]. Далее добавляем новые грани выпуклой оболочки. Необходимо найти их конфликты. Сами грани представляют из себя треугольники, если, конечно, они не были смержены с уже имеющимися гранями. Во втором случае новая грань находится в конфликте с теми же точками, что и старая грань, т.к. смерженные грани компланарны.

3dconvexhullconflictlist.png

Перейдём к первому случаю. Пусть мы добавили точку [math]p_r[/math] и рассматриваем грань [math]f[/math]. [math]e[/math] — ребро, принадлежащее horizon, [math]f_1, f_2[/math] — грани, пересечение которых образовывало [math]e[/math] в старой оболочке. Пусть [math]p_t[/math] — ещё не добавленная точка, из которой видно [math]f[/math], тогда из неё видно и ребро [math]e[/math], причём как в новой, так и в старой выпуклой оболочке (так как новая включает в себя старую). Но это возможно, только если из [math]p_t[/math] видно [math]f_1[/math] или [math]f_2[/math]. Значит, точки, с которыми у [math]f[/math] есть конфликт — это только какие-то из точек, у которых есть конфликт у [math]f_1[/math] и [math]f_2[/math].

Время работы

Лемма (1):
Пусть [math]P[/math] — выпуклый многогранник с [math]n[/math] вершинами. Тогда число его рёбер не превосходит [math]3n - 6[/math], а число его граней — [math]2n - 4[/math].
Доказательство:
[math]\triangleright[/math]
Верхняя грань куба спроецировалась на внешнюю грань графа
«Спроецируем» многогранник на плоскость, как на картинке (будем считать общеизвестным фактом, что выпуклый многогранник планарен). Получили планарный граф, по формуле Эйлера имеем [math]n - n_e + n_f = 2[/math], где [math]n_e[/math] — число рёбер, [math]n_f[/math] — число граней. Каждая грань нашего графа имеет по меньшей мере 3 ребра, каждое ребро инцидентно двум граням, поэтому имеем [math]2 n_e \geqslant 3 n_f[/math] (если не удаётся это понять, можно представить двудольный граф, где слева грани, а справа рёбра. Из каждого ребра исходит ровно 2 вершины, а в каждую грань входит хотя бы 3). Тогда получаем [math]n_f \leqslant 2n - 4[/math], и, подставив это в формулу Эйлера, [math]n_e \leqslant 3n - 6[/math].
[math]\triangleleft[/math]
Лемма (2):
Ожидаемое число граней, создаваемое нашим алгоритмом, не превосходит [math]6n - 20[/math].
Доказательство:
[math]\triangleright[/math]

Рассмотрим добавление точки [math]p_r[/math]. Все грани, добавленные на этом шаге алгоритма, инцидентны этой точке, равно как и добавленные рёбра. Обозначим число инцидентных точке [math]p_i[/math] рёбер (степень вершины; оно же число инцидентных точек) в выпуклой оболочке [math]r[/math] точек как [math]k_{i, r}[/math].

По лемме 1 у многогранника с [math]r[/math] веришнами не больше [math]3r - 6[/math] рёбер. Значит, сумма степеней вершин многогранника не больше [math]6r - 12[/math]. Значит, средняя степень вершины равна [math]6 - 12/r[/math]. Точки берутся в случайном порядке, поэтому можно считать, что ожидаемая степень вершины [math]p_r[/math] равна [math]6 - 12/r[/math]. Это рассуждение верно только для [math]r \gt 4[/math], так как первые четыре точки фиксированы, их суммарная степень равна [math]12[/math]. Посчитаем математическое ожидание [math]k_r[/math]:

[math]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[/math].

Ожидаемое число граней — это число граней в начальном тетраэдре (4 — ваш К.О.) плюс ожидаемое общее число созданных граней при добавлении точек. Поэтому искомое число равно [math]4 + \sum_{r = 5}^{n} E(k_{r, r}) \leqslant 4 + 6(n - 4) = 6n - 20[/math].
[math]\triangleleft[/math]
Теорема:
Время работы алгоритма — [math]O(n \log n)[/math].
Доказательство:
[math]\triangleright[/math]

Шаги перед добавлением точек можно сделать за [math]O(n \log n)[/math]. Очередной шаг требует константного времени, если [math]m_r[/math] — число конфликтных граней для добавляемой точки — равно нулю (то есть когда точка внутри или на границах имеющейся выпуклой оболочки). Иначе этот шаг требует [math]O(m_r)[/math] времени плюс время на удаление видимых рёбер (удалить ребро можно не больше одного раза, поэтому можно считать, что этот шаг лишь изменит константу во времени создания новых рёбер) и изменение графа конфликтов.

Заметим, что [math]m_r[/math] — число граней, удалённых на очередном шаге алгоритма, поэтому по лемме 2 [math]E(\sum_{r = 5}^{n} m_r) = O(n)[/math].

При изменении графа конфликтов на шаге [math]r[/math] требуется время, равное сумме числа конфликтных точек для смежных граней каждого ребра на horizon. Это меньше либо равно числу всех конфликтных точек для всех граней. Утверждается, что оно равно [math]O(n \log n)[/math], и это надо как-то доказать (в де Берге есть, надо разобраться и дополнить), и тогда теорема доказана.
[math]\triangleleft[/math]