How to use Morton Order(z order curve) in range search? -

how use morton order in range search? wiki, in paragraph "use one-dimensional data structures range searching",

it says

"the range being queried (x = 2, ..., 3, y = 2, ..., 6) indicated dotted rectangle. highest z-value (max) 45. in example, value f = 19 encountered when searching data structure in increasing z-value direction. ......bigmin (36 in example).....only search in interval between bigmin , max...."

my questions are:

1) why f 19? why f should not 16?

2) how bigmin?

3) there web blogs demonstrate how range search?

this blog post reasonable job of illustrating process.

when searching rectangular space x=[2,3], y=[2,6]:

1. the minimum z value (12) found interleaving bits of lowest x , y values: 2 , 2, respectively.
2. the maximum z value (45) found interleaving bits of highest x , y values: 3 , 6, respectively.
3. having found min , max z values (12 , 45), have linear range can iterate across guaranteed contain of entries inside of our rectangular space. data within linear range going superset of data care about: data in rectangular space. if iterate across entire range, going find of data care , some. can test each value visit see if it's relevant or not.

an obvious optimization try minimize amount of superfluous data must traverse. largely function of number of 'seams' cross in data -- places 'z' curve has make large jumps continue path (e.g. z value 31 32 below).

this can mitigated employing bigmin , litmax functions identify these seams , navigate rectangle. minimize amount of irrelevant data evaluate, can:

1. keep count of number of consecutive pieces of junk data we've visited.
2. decide on maximum allowable value (maxconsecutivejunkdata) count. blog post linked @ top uses 3 value.
3. if encounter maxconsecutivejunkdata pieces of irrelevant data in row, initiate bigmin , litmax. importantly, @ point @ we've decided use them, we're somewhere within our linear search space (z values 12 45) outside rectangular search space. in wikipedia article, appear have chosen maxconsecutivejunkdata value of 4; started @ z=12 , walked until 4 values outside of rectangle (beyond 15) before deciding time use bigmin. because maxconsecutivejunkdata left tastes, bigmin can used on value in linear range (z values 12 45). confusingly, article shows area 19 on crosshatched because subrange of search optimized out when use bigmin maxconsecutivejunkdata of 4.

when realize we've wandered outside of rectangle far, can conclude rectangle in non-contiguous. bigmin , litmax used identify nature of split. bigmin designed to, given value in linear search space (e.g. 19), find next smallest value inside half of split rectangle larger z values (i.e. jumping 19 36). litmax similar, helping find largest value inside half of split rectangle smaller z values. implementations of bigmin , litmax explained in depth in zdivide function explanation in linked blog post.