Триангуляция Делоне - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:17:38Z

rollbackEdits.php mass rollback

185.86.148.90 в 05:40, 1 сентября 2022

2022-09-01T05:40:09Z

77.234.215.133 в 15:30, 19 февраля 2020

2020-02-19T15:30:56Z

Vlad kv: Исправлена опечатка

2018-01-20T14:14:44Z

Исправлена опечатка

Vlad kv: "ребро должно принадлежать триангуляции с добавленной точкой V" здесь лишнее и будет обосновано только в последующих теоремах

2018-01-20T13:46:54Z

"ребро должно принадлежать триангуляции с добавленной точкой <tex>V</tex>" здесь лишнее и будет обосновано только в последующих теоремах

176.116.241.114: /* Локальный критерий Делоне */

2016-04-06T16:41:52Z

‎Локальный критерий Делоне

194.85.161.2: /* Память */

2016-02-26T22:48:16Z

‎Память

Darkraven: /* Существование триангуляции Делоне */

2015-05-30T11:23:13Z

‎Существование триангуляции Делоне

Itan: /* Существование триангуляции Делоне */

2015-05-18T22:22:24Z

‎Существование триангуляции Делоне

Itan: /* Существование триангуляции Делоне */

2015-05-18T22:18:59Z

‎Существование триангуляции Делоне

← Предыдущая		Версия 16:17, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	== Определение ==		== Определение ==
	{{Определение		{{Определение

← Предыдущая		Версия 05:40, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	== Определение ==		== Определение ==
	{{Определение		{{Определение

← Предыдущая		Версия 15:30, 19 февраля 2020
Строка 1:		Строка 1:
−	~~{{nohate}}~~
	== Определение ==		== Определение ==
	{{Определение		{{Определение

@@ Строка 288: / Строка 288: @@
 <tex>E(\operatorname{deg_{S_k}} (\operatorname{nn} (q, S_{k+1}))) = \frac {1} {C^{|R_{k+1}|}_{|R_k|}} \sum\limits_{R'_{k+1}\subset R_k} \frac {1} {|R_{k+1}|} \sum\limits_{a_i\in R'_{k+1}} \operatorname{deg_{R_k}}(a_i) \operatorname{deg_{NN(R'_{k+1})}}(a_i)</tex>
-По [[#closestlemma|лемме 12]] степень вершины из правой доли графа <tex>NN</tex> не может быть больше шести.
+По [[#closestlemma|лемме 11]] степень вершины из правой доли графа <tex>NN</tex> не может быть больше шести.
 <tex>E(\operatorname{deg_{S_k}} (\operatorname{nn} (q, S_{k+1}))) \le \frac {1} {C^{|R_{k+1}|}_{|R_k|}} \sum\limits_{R'_{k+1}\subset R_k} \frac {1} {|R_{k+1}|} \sum\limits_{a_i\in R'_{k+1}} \operatorname{deg_{R_k}}(a_i) \cdot 6 = \frac {6} {C^{|R_{k+1}|}_{|R_k|} \cdot |R_{k+1}|} \sum\limits_{R'_{k+1}\subset R_k} \sum\limits_{a_i\in R'_{k+1}} \operatorname{deg_{R_k}} (a_i) =

@@ Строка 119: / Строка 119: @@
 |proof=
 [[Файл:Good edge.png|400px|thumb|right|Точка V вставлена в треугольник ABC]]
-Предположим, точка была вставлена не на ребро. Рассмотрим любое из рёбер — пусть это будет ребро <tex>VC</tex>. Проведём окружность, описывающую треугольник <tex>ABC</tex>. По критерию Делоне в ней не будет никаких точек триангуляции. На ребре <tex>VC</tex> можно построить окружность, изнутри касающуюся окружности, описанной вокруг треугольника. В ней тоже нет никаких точек. Значит, для <tex>VC</tex> выполняется критерий Делоне для рёбер, значит, ребро должно принадлежать триангуляции с добавленной точкой <tex>V</tex>, значит, оно хорошее.
+Предположим, точка была вставлена не на ребро. Рассмотрим любое из рёбер — пусть это будет ребро <tex>VC</tex>. Проведём окружность, описывающую треугольник <tex>ABC</tex>. По критерию Делоне в ней не будет никаких точек триангуляции. На ребре <tex>VC</tex> можно построить окружность, изнутри касающуюся окружности, описанной вокруг треугольника. В ней тоже нет никаких точек. Значит, для <tex>VC</tex> выполняется критерий Делоне для рёбер, то есть, оно хорошее.
 Случай, когда точка вставляется на ребро, рассматривается аналогично.

@@ Строка 62: / Строка 62: @@
 == Локальный критерий Делоне ==
 {{Определение
-|definition='''Локальный критерий Делоне''': для пары треугольников, которым принадлежит это ребро, выполняется критерий Делоне (то есть вершина, противолежащая ребру в одном треугольнике, не лежит в окружности, описанной вокруг другого, и наоборот).
+|definition='''Локальный критерий Делоне для ребра''': для пары треугольников, которым принадлежит это ребро, выполняется критерий Делоне (то есть вершина, противолежащая ребру в одном треугольнике, не лежит в окружности, описанной вокруг другого, и наоборот).
 }}
 Будем называть '''хорошими''' те рёбра, для которых выполняется локальный критерий Делоне.

@@ Строка 241: / Строка 241: @@
 Оценим вторую сумму:
-<tex>\sum\limits_{k = \log_{1/p} n + 1}^{\infty} k \cdot p(k) = \leq \sum\limits_{k = \log_{1/p} n}^{\infty} k \cdot n p^k = n \cdot \sum\limits_{k = \log_{1/p} n}^{\infty} k \cdot p^k</tex>
+<tex>\sum\limits_{k = \log_{1/p} n + 1}^{\infty} k \cdot p(k) \leq \sum\limits_{k = \log_{1/p} n}^{\infty} k \cdot n p^k = n \cdot \sum\limits_{k = \log_{1/p} n}^{\infty} k \cdot p^k</tex>
 Рассмотрим эту сумму:
@@ Строка 255: / Строка 255: @@
 Триангуляция для <tex>n</tex> точек занимает <tex>O(n)</tex> памяти. На нулевом уровне <tex>n</tex> точек. На уровне <tex>k</tex> точек <tex>m_k=p \cdot m_{k-1}</tex>. Получим геометрическую прогрессию, сумма которой равна <tex>O(n)</tex>.
 }}
 ==== Время работы ====
 {{Лемма

@@ Строка 26: / Строка 26: @@
 Заметим, что получившееся уравнение является уравнением плоскости: <tex>Ax + By + Cz + D = 0</tex>, то есть, все точки проекции окружности будут лежать в одной плоскости.
-Рассмотрим любую точку внутри данной окружности. Через нее можно привести окружность с центром в точке <tex>(a, b)</tex> и радиусом <tex>r' < r</tex>, тогда плоскость, проходящая через проекцию этой окружности на параболоид будет иметь уравнение <tex>Ax + By + Cz + D' = 0</tex>, то есть, обе плоскости будут параллельны и вторая плоскость будет лежать под плоскостью окружности (поскольку <tex>r' < r</tex>, то <tex>D' = (a^2 + b^2 - r'^2) > (a^2 + b^2 - r^2) = D</tex>).
+Рассмотрим любую точку внутри данной окружности. Через нее можно провести окружность с центром в точке <tex>(a, b)</tex> и радиусом <tex>r' < r</tex>, тогда плоскость, проходящая через проекцию этой окружности на параболоид будет иметь уравнение <tex>Ax + By + Cz + D' = 0</tex>, то есть, обе плоскости будут параллельны и вторая плоскость будет лежать под плоскостью окружности (поскольку <tex>r' < r</tex>, то <tex>D' = (a^2 + b^2 - r'^2) > (a^2 + b^2 - r^2) = D</tex>).
 Аналогично доказывается, что точки лежащие вне окружности лежат над плоскостью.

@@ Строка 24: / Строка 24: @@
 При проецировании, для проекции окружности на параболоид верны оба уравнения: и окружности, и параболоида, поэтому в уравнение окружности вместо <tex>x^2 + y^2</tex> можно подставить <tex>Cz</tex>, получится <tex>(-2a)x + (-2b)y + Cz + (a^2 + b^2 - r^2) = 0</tex>
-Заметим, что получившееся уравнение является уравнением плоскости: <tex>Ax + By + Cz + D = 0</tex>, то есть, все точки окружности будут лежать в одной плоскости.
+Заметим, что получившееся уравнение является уравнением плоскости: <tex>Ax + By + Cz + D = 0</tex>, то есть, все точки проекции окружности будут лежать в одной плоскости.
-Рассмотрим любую точку внутри данной окружности. Через нее можно привести окружность с центром в точке <tex>(a, b)</tex> и радиусом <tex>r' < r</tex>, тогда плоскость, проходящая через проекцию этой окружности на параболоид будет иметь формулу <tex>Ax + By + Cz + D' = 0</tex>, т.е., обе плоскости будут параллельны и вторая плоскость будет лежать под плоскостью окружности (поскольку <tex>r' < r</tex>, то <tex>D' = (a^2 + b^2 - r'^2) > (a^2 + b^2 - r^2) = D</tex>).
+Рассмотрим любую точку внутри данной окружности. Через нее можно привести окружность с центром в точке <tex>(a, b)</tex> и радиусом <tex>r' < r</tex>, тогда плоскость, проходящая через проекцию этой окружности на параболоид будет иметь уравнение <tex>Ax + By + Cz + D' = 0</tex>, то есть, обе плоскости будут параллельны и вторая плоскость будет лежать под плоскостью окружности (поскольку <tex>r' < r</tex>, то <tex>D' = (a^2 + b^2 - r'^2) > (a^2 + b^2 - r^2) = D</tex>).
 Аналогично доказывается, что точки лежащие вне окружности лежат над плоскостью.

@@ Строка 16: / Строка 16: @@
 Окружность, спроецированная на параболоид, находится в одной плоскости. Все точки, лежащие внутри окружности, будут лежать под этой плоскостью. Точки, лежащие вне окружности, будут лежать над плоскостью.
 |proof=
-Рассмотрим окружность с центром в точке <tex>(a, b)</tex> и радиуса <tex>r</tex>, она описывается уравнением: <tex>(x - a)^2 + (y - b)^2 = r^2</tex>.
+Рассмотрим окружность с центром в точке <tex>(a, b)</tex> радиуса <tex>r</tex>, она описывается уравнением: <tex>(x - a)^2 + (y - b)^2 = r^2</tex>.
-Раскроем скобки в уравнении окружности, получим <tex>x^2 - 2ax + a^2 + y^2 - 2by + b^2 = r^2</tex>
+Раскрывая скобки в уравнении окружности, получим <tex>x^2 - 2ax + a^2 + y^2 - 2by + b^2 = r^2</tex>
 Рассмотрим параболоид, пускай его уравнение имеет вид <tex>x^2 + y^2 = Cz</tex>.