is , a node of QO is a structure shown below ; 
structure node { 
structure node x Son;, x Son», * Sons, * Sons ; 
Set—of—Objects S ; 
) 
Now , a recursive algorithm of creating QO is given 
below as the definition of QO. 
Algorithm ; CreatQO(R, SO) 
Procedure , 
step 1: Get a node as the root of the QO, set every 
item of 7 null. 
step 2; Let Ri, where? — 1,2,3,4, is the four quad 
block of R ; For V o € SO ,if R(o) C Rand R(o) ER, 
i = 1,2,3,4, then 
r.S = r.S U (o); 
step 3: Let S0; — (olo € SO — r. S,R(o) CR}, 
à = 1,2,3,4; If SO; is not empty , then create QO: = 
CreatQO() by recursion, and let r. Son; points to QO; , i = 
]1,2.3.4. 
2.2 The operation on QO 
The inserting, deleting and searching are the main basic 
operations on QO . We give the inserting algorithm on 
QO below. 
INSERTQO( 7,0,R ) 
Begin 
if » NULL 
then get a node 7 as the root of QO, and 
set all the items in 7 null. 
if R(o) C- R 
then begin 
r. S — r. S |) (o) ;return; 
end 
Let R; is the ith quad block of R , 
if RO) CR; 
then begin 
if 7. Som =NULL 
then get a node ,and let 7. Son; 
points to it. 
INSERTQOX( r. Son; ,0,R; ) ; 
end ; 
End 
The deleting and searching algorithm are similar to the 
inserting algorithm, so no details are given here. 
Using the inserting algorithm, an algorithm of creating 
QO with time consumption O(N) can be given. 
2.3 QO and position—based queries 
(1) To find the objects at a given position (z,y) ; only 
check the objects stored at the nodes whose corresponding 
84 
quad blocks contain the point (z,y) . 
(2) To open a window on a image ; if the set of nodes 
» Whose corresponding quad blocks intersect with the win- 
dow, is { nd; , nd2,. . . nd.) , then only check the objects 
stored at all the ancestor nodes of nd; , 4 — 1,... ,m , and 
the objects stored at the subtree whose root is nd; . 
(3) To find all the objects contained in or intersecting 
with a given region; At first , look up all the nodes whose 
corresponding quad blocks intersect with the region , then 
check the objects on these nodes. 
2.4 The organization of objects stored at a node 
Because the queries on QO are transferred to search on 
some nodes on the tree, so it is necessary to organize the 
objects stored at a node in a suitable way . A schema is to 
store the objects by a sorted balanced binary tree with the 
size of objects as the key. Using this structure can further 
confine the searching scope and leads to a higher effec- 
tiveness. 
$3 The Querying Effectiveness of QO 
Using QO, the searching in queries are confined at one 
node or some nodes. So, in this section, we will discuss 
the effectiveness by analysing the number of objects 
Stored at a node or a series of nodes. 
To simplify the discuss, we suppose the image corre- 
sponding to a region of unit square [0,17], similarly , 
suppose that the total number of objects on the image is 1. 
The diameter (or size ) 4(R) of a region R is defined as 
d(R) ; max{d(a1 ,%2) |21 5x2 € R). 
Suppose the probability density of d(R) is p(x) , where 
x E [0/31 
3.1 The expected number 5, of objects stored at a node 
Suppose that node nd corresponding to a quad block B 
with size , the expected number of objects stored at nd is Pm 
. We divide pn into two parts, one corresponding to the 
objects whose size is larger than 1/2"*! , the other part 
corresponding to the else, and we use Pm1s fato represent 
them, so , there is pn = pu + Pre 
Because 
ir“: 77 
Pmi x im yz? p(a)da 
yy 
0 
pa <} 7 pe 
where 7 (z) is the probability of the objects with size z in- 
tersecting with the lines which divide B into four equaling 
sub blocks. 
Under a model with equaling probability , it is easy to 
deduce that 7 (x) << E — a? , So we have 
3.2 
sect ' 
spon 
Bar 
one : 
mdm € 
and 
gm iS 
who 
ex]x 
root 
hav 
ther 
lis