Skip quadtree: определение, время работы

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

Описание

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

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].