kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

DSL_2_C: Range Search (kD Tree) (続き)

たとえば領域を10x10の小領域に分けて、それぞれの点がどの領域に
含まれるかあらかじめ決めておけばけっこう速くなるんじゃないか、
など考えつつ
たてよこあみだくじの図を見ていたらちょっとひらめいた

左右に分けて、上下に分けて、を繰り返してるのか
これを覚えておけば2分木ができるってわけだな?
2分木だからlog nのオーダで検索できると?

しかしそれでもたとえば領域全体を含むような検索をされたら
結局時間かかっちゃうよな・・・と思ったら

各クエリについて、与えられた領域内に含まれる点の数は100を超えない。

つまり(点の数が50万に近ければ)ごく一部ってことだな?
なんかピースがはまった感ある
これはいい方向に向かってそうだ

実装できるかな?

まず、左右に見て真ん中あたりにある点を選んで、
その点を通る縦の線をひいて領域を左右に分ける
次に、左右それぞれの領域で、上下の真ん中あたりにある点を選んで、
その点を通る横線をひいて領域を上下に分ける
そういうことだよな

真ん中あたりっていうのはx座標またはy座標でソートして真ん中を選ぶのかな
毎回?大変そうだけどまあ毎回半分になるわけだし
いや、それとも数じゃなくて座標的に真ん中で分けるほうがいいのかな

点を探すところはどうするといいのかまだよく見えてない
与えられた領域と、たてよこあみだくじの領域の対応をどうつければいいのか

都度都度、それぞれの領域に含まれる点を覚えておくのかな?
葉に到達するまで覚えなくても大丈夫?
分ける基準になった点はどっちに入れる?両方?

分割してできた小領域がまるごと調べたい領域に含まれていれば簡単だけど
またがっちゃってる場合はどうする?

細かいところはまだ見えてない
もうちょっと考える