Алгоритм Балабана - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:05:47Z

rollbackEdits.php mass rollback

141.98.9.47 в 06:35, 1 сентября 2022

2022-09-01T06:35:02Z

188.162.64.87: /* Введение */

2015-08-31T10:19:59Z

‎Введение

194.85.161.34: /* Ключевые моменты */ - заменил скобки в картинке

2013-11-30T08:08:24Z

‎Ключевые моменты: - заменил скобки в картинке

194.85.161.34: /* Основные понятия */

2013-11-30T08:03:34Z

‎Основные понятия

194.85.161.34: /* Основные понятия */

2013-11-30T07:56:55Z

‎Основные понятия

194.85.161.34: /* Введение */

2013-11-30T07:54:15Z

‎Введение

194.85.161.34: /* Split */

2013-11-30T07:36:25Z

‎Split

194.85.161.2: /* Ключевые моменты */

2013-11-30T05:48:49Z

‎Ключевые моменты

194.85.161.2 в 00:49, 29 ноября 2013

2013-11-29T00:49:13Z

← Предыдущая		Версия 16:05, 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 Майкл Наки].
−	\|}
−
	{{В разработке}}		{{В разработке}}

← Предыдущая		Версия 06:35, 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 Майкл Наки].
		+	\|}
		+
	{{В разработке}}		{{В разработке}}

@@ Строка 8: / Строка 8: @@
 # Тривиальный детерминированный алгоритм имеет временную сложность <tex>O(n^2)</tex>, и его суть заключается в проверке попарного пересечения отрезков.
-# Сложнее, но эффективнее алгоритм Бентли-Оттмана <ref>[http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Бентли-Оттмана ''Алгоритм Бентли-Оттмана'']</ref> с оценкой сложности <tex>O((n + k)\ log(n)+k)</tex>, в основе которого лежит метод заметающей прямой.
+# Сложнее, но эффективнее алгоритм Бентли-Оттмана <ref>[http://neerc.ifmo.ru/wiki/index.php?title=Алгоритм_Бентли-Оттмана ''Алгоритм Бентли-Оттмана'']</ref> с оценкой сложности <tex>O((n + k) \log n +k)</tex>, в основе которого лежит метод заметающей прямой.
-# Алгоритм, предложенный Чазелле и Едельсбруннером <ref>[http://www.cs.princeton.edu/~chazelle/pubs/IntersectLineSegments.pdf ''An optimal algorithm for intersecting line segments in the plane'']</ref>, имеет лучшую оценку <tex>O(n\ log(n) + k)</tex>, но в отличие от предыдущих методов требует квадратичной памяти.
+# Алгоритм, предложенный Чазелле и Едельсбруннером <ref>[http://www.cs.princeton.edu/~chazelle/pubs/IntersectLineSegments.pdf ''An optimal algorithm for intersecting line segments in the plane'']</ref>, имеет лучшую оценку <tex>O(n \log n + k)</tex>, но в отличие от предыдущих методов требует квадратичной памяти.
-# Оптимальный детерминированный алгоритм был предложен Балабаном <ref>[http://www.cs.sfu.ca/~binay/813.2011/Balaban.pdf ''I.J. Balaban. An optimal algorithm for finding segments intersections. In Proceedings of the Eleventh Annual Symposium on Computational Geometry, ACM Press, New York, 1995. - pp. 211–219.'']</ref> с временной оценкой сложности <tex>O(n\ log(n) + k)</tex> и <tex>O(n)</tex> памяти, где К - число пересекающихся отрезков.
+# Оптимальный детерминированный алгоритм был предложен Балабаном <ref>[http://www.cs.sfu.ca/~binay/813.2011/Balaban.pdf ''I.J. Balaban. An optimal algorithm for finding segments intersections. In Proceedings of the Eleventh Annual Symposium on Computational Geometry, ACM Press, New York, 1995. - pp. 211–219.'']</ref> с временной оценкой сложности <tex>O(n \log(n) + k)</tex> и <tex>O(n)</tex> памяти, где К - число пересекающихся отрезков.
 При количестве отрезков от 2000, и большому количеству пересечений целесообразно использовать алгоритм Балабана. Однако в результате громоздкости и высокой сложности реализации алгоритма, в большинстве практических задач используется алгоритм заметающей прямой Бентли-Оттмана.

@@ Строка 162: / Строка 162: @@
 Наша задача показать, что все операции с узлом <tex>v</tex> происходят за <tex>O(|S_v| + |Int(D_v, S_v')| + (a_v - b_v)logN)</tex>, для этого возьмем во внимание, что <tex>\sum_v |S_v| = O(N \cdot logN + K)</tex> (очевидно, что <tex>\sum_v |Int(D_v, S_v')| \le K</tex>).
-[[Файл:Balaban_pic_2.png|280px|thumb|right|<tex>S_v = (s_1, s_2, s_3, s_4, s_5)</tex>, <tex>L_v = (s_1, s_3)</tex>, <tex>R_v = (s_3, s_4)</tex>, <tex>I_v = (s_2, s_5)</tex>]]
+[[Файл:Balaban_pic_2.png|280px|thumb|right|<tex>S_v = \{s_1, s_2, s_3, s_4, s_5\}</tex>, <tex>L_v = (s_1, s_3)</tex>, <tex>R_v = (s_4, s_3)</tex>, <tex>I_v = \{s_2, s_5\}</tex>]]
 Функция <tex>TreeSearch</tex> похожа на функцию <tex>SearchInStrip</tex>. Основная разница заключается в том, что <tex>SearchInStrip</tex> вызывает себя без изменения полосы, когда <tex>TreeSearch</tex> делит полосу на две части, после чего рекурсивно вызывает себя для них. Другое отличие заключается в том, что множество <tex>S_v</tex> не упорядочено так же, как <tex>L</tex>. В результате мы не можем напрямую использовать функцию <tex>Split</tex> для эффективного деления <tex>S_v</tex>.

@@ Строка 38: / Строка 38: @@
 [[Файл:Balaban_pic_1.png|280px|thumb|right|<tex>D = ((s_1, s_2, s_3), \langle a, b \rangle)</tex>, <tex>Loc(D, s_4) = 0</tex>, <tex>Loc(D, s_5) = 2</tex> или <tex>3</tex>, <tex>Int(D, \{s_4,\ s_5\}) = \{\{s_3,\ s_5\}\}</tex>]]
-Обозначения <tex>Int_{a, b}(S)</tex> и <tex>Int_{a, b}(S, S')</tex> будут использоваться для описания подмножеств <tex>Int(S)</tex> и <tex>Int(S, S')</tex>, состоящих из пересекающихся пар отрезков в пределах полосы <tex>\langle a, b \rangle</tex>. Далее скобки <tex>\{\}</tex> используются для определения неупорядоченных множеств, а скобки <tex>()</tex> используются для определения упорядоченных множеств.
+Обозначения <tex>Int_{a, b}(S)</tex> и <tex>Int_{a, b}(S, S')</tex> будут использоваться для описания подмножеств <tex>Int(S)</tex> и <tex>Int(S, S')</tex>, состоящих из пересекающихся пар отрезков в пределах полосы <tex>\langle a, b \rangle</tex>.
-Введем отношение порядка на множестве отрезков <tex>s_1 <_a s_2</tex> если оба отрезка пересекают вертикальную линию <tex>x = a</tex> и
+Далее фигурные скобки <tex>\{\}</tex> используются для определения неупорядоченных множеств, а круглые скобки <tex>()</tex> используются для определения упорядоченных множеств.
 точка пересечения этой прямой с отрезком <tex>s_1</tex> лежит ниже точки пересечения с <tex>s_2</tex>.
 {{Определение
@@ Строка 47: / Строка 52: @@
 |definition=
 ''Лестница'' <tex>D</tex> — это пара <tex>(Q, \langle a, b \rangle)</tex>, в которой отрезки из множества <tex>Q</tex> удовлетворяют следующим условиям :
-− любой отрезок из <tex>Q</tex> охватывает полосу <tex>\langle a, b \rangle</tex>; <br>
+{{---}} любой отрезок из <tex>Q</tex> охватывает полосу <tex>\langle a, b \rangle</tex>; <br>
-− нет пересечений отрезков внутри лестницы; <br>
+{{---}} нет пересечений отрезков внутри лестницы; <br>
-− <tex>Q</tex> упорядочена по отношению <tex><_a</tex>.
+{{---}} <tex>Q</tex> упорядочена по отношению <tex><_a</tex>.
 Часть отрезков лестницы внутри полосы будем называть '''ступеньками'''.

@@ Строка 22: / Строка 22: @@
 {{Определение
 |definition=
 Будем говорить, что отрезок <tex>s</tex>, с вершинами в точках с абсциссами <tex>l</tex> и <tex>r</tex> :
-- '''охватывает'''(span) полосу <tex>\langle a, b \rangle</tex>, если <tex>l \le a \le b \le r</tex>; <br>
+{{---}} '''охватывает''' (''span'') полосу <tex>\langle a, b \rangle</tex>, если <tex>l \le a \le b \le r</tex>; <br>
 - '''внутренний'''(inner) для полосы <tex>\langle a, b \rangle</tex>, если <tex>a < l < r < b</tex>; <br>
-- '''пересекает'''(cross) полосу <tex>\langle a, b \rangle</tex> в других случаях.
+{{---}} '''внутренний''' (''inner'') для полосы <tex>\langle a, b \rangle</tex>, если <tex>a < l < r < b</tex>; <br>
 }}

@@ Строка 96: / Строка 96: @@
               добавить <tex>s_j</tex> в конец <tex>Q;</tex>
           '''else'''
-              добавить <tex>s_j</tex> в конец <tex>L’;</tex>
+              добавить <tex>s_j</tex> в конец <tex>L';</tex>
   <tex>\}</tex>

@@ Строка 127: / Строка 127: @@
 Давайте разберемся с алгоритмом более подробно:
-Не умаляя общности, предположим, что все пересечения и вершины отрезков имеют разные абсциссы (в конечном счете, их можно будет отсортировать введением дополнительных свойств). Будем рассматривать целые координаты на промежутке <tex>[1, 2N]</tex>. Пусть <tex>p_i</tex> и <tex>s(i)</tex> будут координатами вершин <tex>i</tex>-того отрезка.
+Не умаляя общности, предположим, что все пересечения и вершины отрезков имеют разные абсциссы (в конечном счете, их можно будет отсортировать введением дополнительных свойств). Будем рассматривать целые координаты на промежутке <tex>[1, 2N]</tex>. Обозначим через <tex>p_i</tex> слева направо конец отрезка множества <tex>S_0</tex>, а через <tex>s(i)</tex> отрезок, которому он принадлежит соответственно.
 Основная задача нашего алгоритма, это рекурсивная функция <tex>TreeSearch</tex>. Соединим каждый вызов функции с узлом некоего двоичного дерева (далее ''рекурсивное дерево''). Соответствующим узлом отметим все значения, множества и параметры вызова. Обозначим множество внутренних вершин за <tex>V</tex>.

@@ Строка 26: / Строка 26: @@
 |definition=
 Будем говорить, что отрезок <tex>s</tex>, с вершинами в точках с абсциссами <tex>l</tex> и <tex>r</tex> :
-- '''содержит'''(span) полосу <tex>\langle a, b \rangle</tex>, если <tex>l \le a \le b \le r</tex>; <br>
+- '''охватывает'''(span) полосу <tex>\langle a, b \rangle</tex>, если <tex>l \le a \le b \le r</tex>; <br>
 - '''внутренний'''(inner) для полосы <tex>\langle a, b \rangle</tex>, если <tex>a < l < r < b</tex>; <br>
 - '''пересекает'''(cross) полосу <tex>\langle a, b \rangle</tex> в других случаях.
@@ Строка 48: / Строка 48: @@
 |definition=
 ''Лестница'' <tex>D</tex> — это пара <tex>(Q, \langle a, b \rangle)</tex>, в которой отрезки из множества <tex>Q</tex> удовлетворяют следующим условиям :
-− любой отрезок из <tex>Q</tex> содержит полосу <tex>\langle a, b \rangle</tex>; <br>
+− любой отрезок из <tex>Q</tex> охватывает полосу <tex>\langle a, b \rangle</tex>; <br>
 − нет пересечений отрезков внутри лестницы; <br>
 − <tex>Q</tex> упорядочена по отношению <tex><_a</tex>.
@@ Строка 57: / Строка 57: @@
 {{Определение
 |definition=
-Будем называть лестницу <tex>D</tex> '''полной''' относительно множества отрезков <tex>S</tex>, если каждый отрезок из <tex>S</tex> либо не содержит полосу <tex>\langle a, b \rangle</tex>, либо пересекает хотя бы одну из ступенек из множества <tex>D</tex>.
+Будем называть лестницу <tex>D</tex> '''полной''' относительно множества отрезков <tex>S</tex>, если каждый отрезок из <tex>S</tex> либо не охватывает полосу <tex>\langle a, b \rangle</tex>, либо пересекает хотя бы одну из ступенек из множества <tex>D</tex>.
 }}
@@ Строка 84: / Строка 84: @@
 ===Split===
-Функция <tex>Split</tex> разделяет входное множество отрезков <tex>L</tex>, содержащих некоторую полосу <tex>\langle a, b \rangle</tex>, на подмножества <tex>Q</tex> и <tex>L'</tex> так, что лестница <tex>(Q, \langle a, b \rangle)</tex> полна относительно множества отрезков <tex>L'</tex>.
+Функция <tex>Split</tex> разделяет входное множество отрезков <tex>L</tex>, охватывающих некоторую полосу <tex>\langle a, b \rangle</tex>, на подмножества <tex>Q</tex> и <tex>L'</tex> так, что лестница <tex>(Q, \langle a, b \rangle)</tex> полна относительно множества отрезков <tex>L'</tex>.
   Пусть <tex>L = (s_1 ,..., s_k)</tex>, где <tex>s_i <_a s_{i+1}</tex>
@@ Строка 93: / Строка 93: @@
           '''if''' отрезок <tex>S_j</tex> не пересекает
           последний отрезок из <tex>Q</tex> внутри полосы <tex>\langle a, b \rangle</tex>
-          и при этом содержит её '''then'''
+          и при этом охватывает её '''then'''
               добавить <tex>s_j</tex> в конец <tex>Q;</tex>
           '''else'''