Квадродеревья - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:05:50Z

rollbackEdits.php mass rollback

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

2022-09-01T06:27:42Z

94.190.127.191: /* Леммы и теоремы */

2020-03-27T14:02:36Z

‎Леммы и теоремы

188.227.78.184: /* О размерах сжатого квадродерева */

2015-03-11T11:28:05Z

‎О размерах сжатого квадродерева

188.227.78.184: /* О размерах сжатого квадродерева */

2015-03-11T11:08:46Z

‎О размерах сжатого квадродерева

Gromak: переименовал Квадродеревья и перечисление точек в произвольном прямоугольнике (статика) в Квадродеревья: Что-то пошло не так

2014-01-20T09:12:46Z

переименовал Квадродеревья и перечисление точек в произвольном прямоугольнике (статика) в Квадродеревья: Что-то пошло не так

Gromak в 09:10, 20 января 2014

2014-01-20T09:10:49Z

Gromak в 13:59, 17 января 2014

2014-01-17T13:59:24Z

Gromak в 19:46, 15 января 2014

2014-01-15T19:46:06Z

194.85.161.2: очепятки

2014-01-15T04:10:45Z

очепятки

← Предыдущая		Версия 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:27, 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 Майкл Наки].
		+	\|}
		+
	''В списке билетов была опечатка, поэтому возникла путаница во многих местах. В этой статье оставляю просто всё полезное (и не очень) про квадродеревья, потому что нужно для скип-квадродерева.''		''В списке билетов была опечатка, поэтому возникла путаница во многих местах. В этой статье оставляю просто всё полезное (и не очень) про квадродеревья, потому что нужно для скип-квадродерева.''

@@ Строка 16: / Строка 16: @@
 {{Лемма
 |statement=
-Глубина квадродерева для множества точек <tex>P</tex> не превосходит <tex>\log_2(s / c) + 3/2</tex>, где <tex>c</tex> {{---}} наименьшее расстояние между двумя точками из <tex>P</tex>, а <tex>s</tex> {{---}} сторона квадрата, с которого начинается построение квадродерева.
+Глубина квадродерева для множества точек <tex>P</tex> не превосходит <tex>\log_2(s / c) + 1/2</tex>, где <tex>c</tex> {{---}} наименьшее расстояние между двумя точками из <tex>P</tex>, а <tex>s</tex> {{---}} сторона квадрата, с которого начинается построение квадродерева.
 |proof=
 Сторона квадрата на глубине <tex>i</tex>, очевидно, равна <tex>s / 2^i</tex>. Максимальное расстояние между двумя точками внутри квадрата достигается, когда они являются вершинами диагонали, то есть на глубине <tex>i</tex> расстояние между любыми двумя точками в одном квадрате не превосходит <tex>s \sqrt 2 / 2^i</tex>. Поскольку внутренняя вершина квадродерева содержит хотя бы 2 точки в соответствующем ей квадрате, то <tex>s \sqrt 2 / 2^i \geq c</tex>, так как <tex>c</tex> {{---}} минимальное расстояние между точками в <tex>P</tex>. Отсюда следует, что <tex>i \leq \log_2(s \sqrt 2 / c) = \log_2 (s / c) + 1/2</tex>. Значит, глубина любой внутренней вершины не превосходит <tex>\log_2 (s / c) + 1/2</tex>, из чего следует утверждение леммы  (так как самый глубокий лист лежит на 1 глубже самой глубокой внутренней вершины).

@@ Строка 88: / Строка 88: @@
 Как отмечалось в представленной выше теореме, достаточно доказать оценку <tex>O(n)</tex> для числа интересных квадратов. Докажем по индукции, что в квадродереве для <tex>n</tex> точек количество интересных квадратов меньше либо равно <tex>n</tex>:
 * для <tex>n = 1</tex> это очевидно;
-* пусть в квадродереве <tex>n > 1</tex> точек. Рассмотрим корень, у него обязательно должно быть хотя бы 2 непустых ребёнка. Если хотя бы один из детей является точкой, то остальные непустые дети являются деревьями, в которых суммарно не больше <tex>n - 1</tex> точек (и в каждом их меньше <tex>n</tex>). Значит, в них суммарно не больше <tex>n - 1</tex> интересных квадратов (по индукционному предположению). Следовательно, во всём квадродереве не больше <tex>n</tex> интересных квадратов. Если же все непустые дети корня являются интересными квадратами, то мы всё равно можем применить индукционное предположение ко всем детям и получить то же самое, поскольку во всех поддеревьях будет меньше <tex>n</tex> точек (ибо их суммарно <tex>n</tex> и везде есть хотя бы одна, так как дети непустые).
+* пусть доказано для квадродерева для <tex>n - 1</tex> точек. Добавим новую точку <tex>x</tex>: сначала найдём наименьший интересный квадрат <tex>p(x)</tex>, который её содержит. Если <tex>x</tex> находится в его пустой четверти, то просто добавляем <tex>x</tex> как лист, не изменив число интересных квадратов. Если же четверть <tex>p(x)</tex> в которую необходимо вставить <tex>x</tex>, уже содержит точку <tex>y</tex>( или интересный квадрат <tex>r</tex>), то мы можем добавить в дерево интересный квадрат, который будет содержать <tex>x</tex> и <tex>y</tex> в разных четвертях. Таким образом, при добавлении точки мы увеличиваем количество интересных квадратов не более, чем на один.
 Таким образом, квадродерево для <tex>n</tex> точек имеет <tex>O(n)</tex> вершин. Глубина, очевидно, тоже <tex>O(n)</tex>, поскольку на каждом уровне есть хотя бы одна вершина (здесь под вершинами имеются в виду узлы в дереве). При этом оценки получше нет (то есть глубина <tex>\Theta(n)</tex>). На картинке в правом дереве можно на место левого нижнего красного кружка поставить опять такое дерево и так делать сколь угодно долго, получим глубину <tex>\Theta(n)</tex>.

@@ Строка 86: / Строка 86: @@
 Сжатое квадродерево для <tex>n</tex> точек имеет <tex>O(n)</tex> вершин и глубину <tex>O(n)</tex>.
 |proof=
-Как отмечалось в представленной выше теореме, достаточно доказать оценку <tex>O(n)</tex> для числа внутренних вершин, каждая из которых является интересным квадратом (Кэп: то есть для числа интересных квадратов это надо доказать). Докажем по индукции, что в квадродереве для <tex>n</tex> точек количество интересных квадратов меньше либо равно <tex>n</tex>:
+Как отмечалось в представленной выше теореме, достаточно доказать оценку <tex>O(n)</tex> для числа интересных квадратов. Докажем по индукции, что в квадродереве для <tex>n</tex> точек количество интересных квадратов меньше либо равно <tex>n</tex>:
 * для <tex>n = 1</tex> это очевидно;
 * пусть в квадродереве <tex>n > 1</tex> точек. Рассмотрим корень, у него обязательно должно быть хотя бы 2 непустых ребёнка. Если хотя бы один из детей является точкой, то остальные непустые дети являются деревьями, в которых суммарно не больше <tex>n - 1</tex> точек (и в каждом их меньше <tex>n</tex>). Значит, в них суммарно не больше <tex>n - 1</tex> интересных квадратов (по индукционному предположению). Следовательно, во всём квадродереве не больше <tex>n</tex> интересных квадратов. Если же все непустые дети корня являются интересными квадратами, то мы всё равно можем применить индукционное предположение ко всем детям и получить то же самое, поскольку во всех поддеревьях будет меньше <tex>n</tex> точек (ибо их суммарно <tex>n</tex> и везде есть хотя бы одна, так как дети непустые).

← Предыдущая	Версия 09:12, 20 января 2014
(нет различий)

@@ Строка 1: / Строка 1: @@
-'''Статус конспекта:'''
+''В списке билетов была опечатка, поэтому возникла путаница во многих местах. В этой статье оставляю просто всё полезное (и не очень) про квадродеревья, потому что нужно для скип-квадродерева.''
 == Определение и построение ==
 '''Квадродерево''' {{---}} дерево, каждая внутренняя вершина которого содержит 4 ребёнка. Любому узлу квадродерева соответствует некоторый квадрат. Если внутренней вершине <tex>v</tex> соответствует какой-то квадрат <tex>a</tex>, то её детям соответствуют четверти квадрата <tex>a</tex> (см. картинку).
@@ Строка 10: / Строка 6: @@
 [[Файл:Quadtree.png | 500px | thumb | По картинке должно быть понятно]]
-Вообще говоря, квадродеревья могут быть использованы для разных целей и хранить разные данные, но нам они нужны для перечисления точек в произвольном прямоугольнике, соответственно, хранить в них будем какой-то набор точек.
+Вообще говоря, квадродеревья могут быть использованы для разных целей и хранить разные данные, но мы хранить в них будем какой-то набор точек на плоскости.
 Пусть дано множество точек <tex>P</tex>, для которого нужно построить квадродерево. Начнём с некоторого квадрата <tex>\sigma</tex>, содержащего все точки из <tex>P</tex>. Если он не дан явно, его можно легко найти за линейное время от числа вершин. Пусть <tex>\sigma = [x_0, x_1] \times [y_0, y_1]</tex>. Обозначим <tex>x_m = (x_0 + x_1) / 2; y_m = (y_0 + y_1) / 2</tex>. Тогда:
@@ Строка 39: / Строка 35: @@
 == Перечисление точек в произвольном прямоугольнике ==
 Пусть на вход подаётся некоторый прямоугольник <tex>M</tex>, для которого надо вернуть все точки из множества <tex>P</tex>, которые принадлежат этому прямоугольнику.
@@ Строка 65: / Строка 62: @@
 Короче, я не знаю, как это доказать, и мне кажется, что это не так. Если нам подали прямоугольник, содержащий все точки, то мы пройдём по всем вершинам, которых <tex>O(d \cdot n)</tex> (так написано в книжке, и лучшей оценки, видимо, нет). Возможно, я неправильно понимаю, что от нас хотят. Может быть, можно придумать какие-то оптимизации, ибо так совсем печальная оценка на запрос получается. Также могу предположить, что оценку времени можно улучшить, использовав функцию от размера ответа, но опять же не могу придумать/найти, как это сделать.
 == Сбалансированное квадродерево ==
 Квадродерево называется '''сбалансированным''', если для соответствующего ему разбиения плоскости на квадраты верно, что для любых двух соседних квадратов их стороны отличаются не более чем в два раза.
-Тут можно ещё что-то написать, но вроде это не нужно, поэтому оставлю только определение.
+Они нужны для каких-то там задач, но нам не нужны, поэтому ничего писать не буду.
 == Сжатое квадродерево ==

@@ Строка 33: / Строка 33: @@
 Поскольку каждая внутренняя вершина имеет четырёх детей, то суммарное число листьев будет <tex>3i + 1</tex>, где <tex>i</tex> {{---}} число внутренних вершин. Поэтому достаточно доказать оценки лишь для внутренних вершин.
-Каждая внутренняя вершина содержит хотя бы одну точку в соответствующем ей квадрате. Заметим, что квадраты с одного уровня не пересекаются и полностью покрывают весь исходный квадрат (в котором <tex>n</tex> точек). Значит, число внутренних вершин одного уровня не может первосходить <tex>n</tex>. Из этого следует, что всего внутренних вершин <tex>O(d \cdot n)</tex>.
+Каждая внутренняя вершина содержит хотя бы одну точку в соответствующем ей квадрате. Заметим, что квадраты с одного уровня не пересекаются и полностью покрывают весь исходный квадрат (в котором <tex>n</tex> точек). Значит, число внутренних вершин одного уровня не может превосходить <tex>n</tex>. Из этого следует, что всего внутренних вершин <tex>O(d \cdot n)</tex>.
-При построении квадродерева наиболее длительная операция на каждом шаге {{---}} распределение точек по четвертям текущего квадрата. Таким образом, время, затрачиваемое на одну внутренню вершину, линейно зависит от числа точек в соответствующем ей квадрате. Как отмечалось выше, на одном уровне суммарно во всех внутренних вершинах не больше <tex>n</tex> точек, из чего следует доказываемая оценка.
+При построении квадродерева наиболее длительная операция на каждом шаге {{---}} распределение точек по четвертям текущего квадрата. Таким образом, время, затрачиваемое на одну внутреннюю вершину, линейно зависит от числа точек в соответствующем ей квадрате. Как отмечалось выше, на одном уровне суммарно во всех внутренних вершинах не больше <tex>n</tex> точек, из чего следует доказываемая оценка.
 }}