next up previous
Next: 4 $BN3;R%G!<%?$H@~7A%j%9%H(B Up: $B7W;;E7J83X(B II $BBh(B10$B2s(B $B%G!<%?9=B$$H%"%k%4%j%:%`(B(1) Previous: 2 $B=ENOB?BNLdBj(B

3 $B%D%j!

$B7W;;NL$r8:$i$9$K$O!"1s$/$NN3;R$rE,Ev$K$^$H$a$?$$!#Nc$($P(B $B1s$/$NJ}$NN3;R$N$+$?$^$j$r$=$l$i$N=E?4$GCV$-49$($F$b$$$$$7!"9b$$@:EY$,(B $BI,MW$J$iB?=E6KE83+$b9M$($i$l$k!#1s$/$K$$$/$K=>$C$F$+$?$^$j$rBg$-$/$7$F(B $B$$$1$P!"D>4QE*$K$O0l$D$NN3;R$X$NNO$r(B $O(\log N)$ $B$G7W;;$G$-!"A4N3;R$X(B $B$NNO$G$"$l$P$=$N(B $N$$BG\$N(B$O(N\log N)$ $B$G7W;;$G$-$k$3$H$K$J$k!#(B

$B$b$A$m$s!"$3$3$GLdBj$J$N$O$I$&$d$C$F$&$^$/N3;R$r$+$?$^$j$KJ,$1$k$+$H$$(B $B$&$3$H$G$"$k!#$"$kN3;R$X$NNO$r7W;;$9$k$N$KE,$7$?J,$1J}$r8+$D$1$k$K$O!"(B $B$9$/$J$/$H$b0lEY$OA4N3;R$r$_$J$$$H$$$1$J$$!#=>$C$F!"$=$N7W;;NL$O(B $O(N)$ $B$h$j>.$5$/$O$J$$!#N3;RKh$KJL$NJ,$1J}$r$7$?$i!"$=$l$@$1$G7W;;NL(B $B$,(B $O(N^2)$$B$K$J$C$F$7$^$&!#(B

$B$3$NLdBj$O!"$9$Y$F$NN3;R$K;H$($kHFMQ$NJ,$1J}$H$$$&$N$r$"$i$+$8$a9=@.$9(B $B$k$3$H$,$G$-$l$P2r7h$9$k!#$=$l$r$9$k$N$,%D%j!<9=B$$K$h$k3,AXE*$J6u4VJ,(B $B3d$H$$$&$3$H$K$J$k!#(B

$B?^$G@bL@$7$h$&!#(B3$B.$G$"$kI,MW$O$J$$$,!"Bg$-$/(B $B$F$bL5BL$J$@$1$J$N$GIaDL$O$=$3$=$3>.$5$/$H$k!#$3$l$r!"$^$:(B4$B$D$N>.@5J}(B $B7A(B($B%;%k(B)$B$K$o$1$k!#$G!"$=$N$=$l$>$l$r$5$i$K(B4$B$D$K$o$1$k$H$$$&$N$r:F5"E*(B $B$K7+$jJV$7$F$$$/!#(B

Figure 1: $B#4J,LZ$N9=C[(B
\begin{figure}\begin{center}
\leavevmode
\epsfxsize =5cm
\epsffile{quadtree.eps}...
...e{quadtree2.eps}\epsfxsize =5cm
\epsffile{quadtree3.eps}\end{center}\end{figure}

$BN3;R$,(B0$B8D$^$?$O(B1$B8D$7$+$J$/$J$C$?$H$3$m$G;_$a$k!#$3$N(B $B6u4V!JJ?LL!KJ,3d$KBP1~$7$?%D%j!<9=B$$r9M$($k$H!":,$KA4BN$N@5J}7A$KBP1~(B $B$9$k@aE@$,$"$j!"$=$N2<$K(B4$B$D$N>.@5J}7A!"$5$i$K$=$N2<$K$=$N$=$l$>$l$NCf(B $B$N(B4$B$D(B$\cdots$ $B$HB3$$$F$$$C$F!"%D%j!<$NMU$K$ON3;R(B1$B$D(B1$B$D$,$/$k$3$H$K$J$k!#(B $B$3$NJ}K!$G$O!"N3;R$N?tL)EY$,9b$$$H$3$m$G$O:Y$+$/!"$=$&$G$J$$$H$3$m$G$O(B $BAF$$$H$$$&0UL#$G!"E,1~E*$J9=B$$, $B

\begin{displaymath}
$B$  

$B!#%h%9%9%O%c%[!&!"x&%K!"!"!"v#%i!"%)!"%N!"%r!"%)!"%[%M%9%Ht&%R!"%^%H%U%;~&%^!<%O%$%7!"%[!"$&$J4p=`$r;H$&!#(B


\begin{displaymath}
\frac{l}{d} < \theta\nonumber
\end{displaymath}  

$B$3$3$G(B $d$ $B$ON3;R$H@aE@$N=E?4$N5wN%!"(B $l$ $B$O@aE@$KBP1~$9$kN)J}BN$N0lJU(B $B$ND9$5$G$"$k!#%Q%i%a!<%?(B$\theta$$B$O8+9~$_3Q$H$$$o$l$kNL$G$"$j!"7W;;@:EY(B $B$H7W;;NL$r@)8f$9$k!#9b$$@:EY$rF@$?$1$l$P(B $\theta$ $B$r>.$5$/$9$l$P$$$$$,!"(B $BA26aE*$K$O(B $\theta^{-3}$$B$KHfNc$7$F7W;;NL$,A}$($k!#7W;;@:EY$r$"$2$k$b$&(B $B0l$D$NJ}K!$O!"=E?4$@$1$r9M$($k$N$G$J$/B?=E6KE83+$r:n$C$F$*$/$3$H$G$"$k!#(B

$B%D%j!pJs$O7W;;$G$-$k!#B?=E6K(B $BE83+$NE83+78?t$K$D$$$F$b!J7W;;$OHK;($G$"$k$,86M}E*$K$O!K$*$J$8$3$H$G$"(B $B$k!#(B



Jun Makino
$BJ?@.(B18$BG/(B1$B7n(B16$BF|(B