Skip quadtree: определение, время работы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 24: Строка 24:
 
О количестве шагов на одном уровне
 
О количестве шагов на одном уровне
 
|statement=
 
|statement=
На каждом уровне совершается <tex>O(1)</tex> шагов поиска.
+
На каждом уровне совершается <tex>O(1)</tex> шагов поиска для любой точки <tex>x</tex>.
 
|proof=
 
|proof=
ЫЫЫ
+
Пусть в <tex>Q_i</tex> (то есть на <tex>i</tex>-ом уровне) поиск точки <tex>x</tex>, начинающийся с корня, проходит по квадратам <tex>p_0, p_1, \dots, p_m</tex>. Пусть случайная величина <tex>j</tex> {{---}} количество шагов поиска в <tex>Q_i</tex>, тогда <tex>p_{m - j}</tex> {{---}} последний квадрат из <tex>p_0, p_1, \dots, p_m</tex>, являющийся интересным в <tex>Q_{i + 1}</tex>.
 +
 
 +
Оценим вероятность того, что делается <tex>j</tex> шагов. Забьём на случай <tex>j = 0</tex>, так как он не важен при расчёте мат. ожидания. На пути <tex>p_{m - j + 1} \dots, p_m</tex> будет хотя бы <tex>j + 1</tex> непустых четвертинок. У первого квадрата на этом пути есть хотя бы 2 непустых четвертинки, одна из них {{---}} следующий квадрат на пути, в котором тоже хотя бы 2 непустых четвертинки, и так далее. В последнем квадрате просто хотя бы 2 непустых четвертинки. Чтобы
 +
<tex>p_{m - j}</tex> был последним из <tex>p_0, p_1, \dots, p_m</tex> интересным квадратом в <tex>Q_{i + 1}</tex> небходимо, чтобы среди этих <tex>j + 1</tex> непустых четвертинок только одна (вероятность этого назовём <tex>Pr_1</tex>) или ноль (вероятность этого назовём <tex>Pr_0</tex>) были непустыми в <tex>Q_{i + 1}</tex>. Иначе, если будет хотя бы 2 непустые четвертинки, то их наименьший общий предок в дереве будет интересным квадратом и будет находиться глубже <tex>p_{m - j}</tex>. Таким образом, искомая вероятность не превосходит <tex>Pr_0 + Pr_1</tex>.
 +
 
 +
''Лично мне утверждение из предыдущего абзаца далось с трудом, если у вас тоже всё очень плохо, попробуйте напрячь мозг и залипнуть в картинку, вдруг поможет''
 +
 
 +
<tex>Pr_0 \leq p^{(j + 1)}</tex>, потому что это в сущности вероятность того, что ни одна точка из как минимум <tex>j + 1</tex> непустых четвертинок не попала на уровень выше.
 +
 
 +
<tex>Pr_1 \leq (j + 1) \cdot p^{(j + 1)}</tex>, потому что это в сущности вероятность того, что ровно одна точка из как минимум <tex>j + 1</tex> непустых четвертинок не попала на уровень выше.
 +
 
 +
''В общем, если чуть подумать, оценки на <tex>Pr_0</tex> и <tex>Pr_1</tex> довольно ясны.''
 +
 
 +
<tex>E(j) = \sum\limits_{j = 1}^{m} j \cdot Pr(j) \leq \sum\limits_{j = 1}^{m} j \cdot (p^{(j + 1)} + (j + 1) \cdot p^{(j + 1)}) \leq \sum\limits_{j = 1}^{\infty} j \cdot (p^{(j + 1)} + (j + 1) \cdot p^{(j + 1)})</tex>
 +
 
 +
В общем, если так подумать, это <tex>O(1)</tex>. Мне пока лень совсем строго написать, но вообще и так понятно. Разумеется, при условии <tex>p \in (0, 1)</tex>.
 +
 
 
}}
 
}}
 
== Источник ==
 
== Источник ==
 
http://arxiv.org/pdf/cs.cg/0507049.pdf
 
http://arxiv.org/pdf/cs.cg/0507049.pdf

Версия 21:18, 7 января 2014

Эта статья находится в разработке!


Описание

По картинке должно быть понятно

Skip quadtree — как skip list, только вместо list'а quadtree. Поэтому желательно знать, что такое skip list, и необходимо знать, что такое сжатое квадродерево. В данной статье будет рассматриваться только рандомизированая версия этой структуры, потому что больше и не нужно, кажется.

The randomized skip quadtree — последовательность сжатых квадродеревьев над последовательностью подмножеств некоего исходного множества [math]S[/math]. [math]S_0 = S[/math], в [math]S_1[/math] каждый элемент из [math]S_0[/math] входит с вероятностью [math]p[/math] и так далее. The randomized skip quadtree состоит из последовательности [math]\{Q_i\}[/math], где [math]Q_i[/math] — сжатое квадродерево над множеством [math]S_i[/math]. Будем называть эти квадродеревья уровнями, при этом нулевой уровень содержит в точности точки из [math]S[/math]. Заметим, что если какой-то квадрат интересный в [math]Q_i[/math], то он интересный и в [math]Q_{i-1}[/math].

Операции над skip quadtree

Будем для каждого интересного квадрата на каждом уровне хранить указатели на тот же квадрат уровнем ниже и уровнем выше (если есть).

Локализация выполняется аналогично сжатому квадродереву. Под локализацией под разумевается, что мы хотим найти минимальный интересный квадрат задержащий данную точку (содержит геометрически, в самом дереве её может не быть, тут, возможно, правильнее сказать «пересекает»). Сначала локализуемся в квадродереве наибольшего уровня, начиная с его корня. Затем локализуемся в квадродереве уровня ниже, начиная уже не с корня, а с того квадрата, который нашли на прошлом уровне. И так далее, пока не дойдём до дна.

Для добавления сначала надо локализоваться. При этом мы локализуемся сразу на всех уровнях (так уж устроен процесс). Дальше добавляемся в нулевой уровень, затем с вероятностью [math]p[/math] добавляемся на уровень выше и так далее до первого недобавления. При этом количество уровней должно увеличиться максимум на 1, то есть, если появился новый уровень, то процесс точно заканчивается.

Удаление совсем просто: локализуемся, удаляем со всех уровней, на которых есть.

Время работы

Лемма (О количестве шагов на одном уровне):
На каждом уровне совершается [math]O(1)[/math] шагов поиска для любой точки [math]x[/math].
Доказательство:
[math]\triangleright[/math]

Пусть в [math]Q_i[/math] (то есть на [math]i[/math]-ом уровне) поиск точки [math]x[/math], начинающийся с корня, проходит по квадратам [math]p_0, p_1, \dots, p_m[/math]. Пусть случайная величина [math]j[/math] — количество шагов поиска в [math]Q_i[/math], тогда [math]p_{m - j}[/math] — последний квадрат из [math]p_0, p_1, \dots, p_m[/math], являющийся интересным в [math]Q_{i + 1}[/math].

Оценим вероятность того, что делается [math]j[/math] шагов. Забьём на случай [math]j = 0[/math], так как он не важен при расчёте мат. ожидания. На пути [math]p_{m - j + 1} \dots, p_m[/math] будет хотя бы [math]j + 1[/math] непустых четвертинок. У первого квадрата на этом пути есть хотя бы 2 непустых четвертинки, одна из них — следующий квадрат на пути, в котором тоже хотя бы 2 непустых четвертинки, и так далее. В последнем квадрате просто хотя бы 2 непустых четвертинки. Чтобы [math]p_{m - j}[/math] был последним из [math]p_0, p_1, \dots, p_m[/math] интересным квадратом в [math]Q_{i + 1}[/math] небходимо, чтобы среди этих [math]j + 1[/math] непустых четвертинок только одна (вероятность этого назовём [math]Pr_1[/math]) или ноль (вероятность этого назовём [math]Pr_0[/math]) были непустыми в [math]Q_{i + 1}[/math]. Иначе, если будет хотя бы 2 непустые четвертинки, то их наименьший общий предок в дереве будет интересным квадратом и будет находиться глубже [math]p_{m - j}[/math]. Таким образом, искомая вероятность не превосходит [math]Pr_0 + Pr_1[/math].

Лично мне утверждение из предыдущего абзаца далось с трудом, если у вас тоже всё очень плохо, попробуйте напрячь мозг и залипнуть в картинку, вдруг поможет

[math]Pr_0 \leq p^{(j + 1)}[/math], потому что это в сущности вероятность того, что ни одна точка из как минимум [math]j + 1[/math] непустых четвертинок не попала на уровень выше.

[math]Pr_1 \leq (j + 1) \cdot p^{(j + 1)}[/math], потому что это в сущности вероятность того, что ровно одна точка из как минимум [math]j + 1[/math] непустых четвертинок не попала на уровень выше.

В общем, если чуть подумать, оценки на [math]Pr_0[/math] и [math]Pr_1[/math] довольно ясны.

[math]E(j) = \sum\limits_{j = 1}^{m} j \cdot Pr(j) \leq \sum\limits_{j = 1}^{m} j \cdot (p^{(j + 1)} + (j + 1) \cdot p^{(j + 1)}) \leq \sum\limits_{j = 1}^{\infty} j \cdot (p^{(j + 1)} + (j + 1) \cdot p^{(j + 1)})[/math]

В общем, если так подумать, это [math]O(1)[/math]. Мне пока лень совсем строго написать, но вообще и так понятно. Разумеется, при условии [math]p \in (0, 1)[/math].
[math]\triangleleft[/math]

Источник

http://arxiv.org/pdf/cs.cg/0507049.pdf