第 4 章 クエリをサポートする方形描 画の符号画の符号
4.3 隣接クエリ
48 第4章 クエリをサポートする方形描画の符号
4.3. 隣接クエリ 49
(b)
f
S2 S3 S1
S0
s1=
S1 S2 S3
f
(c) (a)
(d)
f
e3 e2
e1
e4
s'2=
}
east(f)
edge(f ,e )4 edge(f ,e )3
edge(f ,e )2 edge(f ,e )1 f
w3 w2 w1
s'2=
}
west(f) edge(f ,w )1 edge(f ,w )2 edge(f ,w )3
f
e1 n1 n2 n3
s'2=
}
east(f)
}
east(n )1 west(n )2 east(n )2 west(n )3 west(e )1
}} }}
edge(n ,n )1 2 edge(n ,n )2 3 edge(f ,e )1
[ [ [ [
[ [ [ [ ] ] ] ]
][ ] ] ( ( )( )( ) )
[ [ [ ]]]
図 4.8: クエリの解の求め方の説明図
50 第4章 クエリをサポートする方形描画の符号
(b)
(c) (a)
(d) S'2=
Rj Li
a b c d
[ [ [ ] ] ] ]
S'2=
Rj Li
a b c d
[ [ [ ] ] ] ]
S'2=
Rj Li
a b c d
[ [ [ ] ] ] ]
S'2=
Rj Li
a b c d
[ [ [ ] ] ] ]
図 4.9: (wa)クエリの説明図
S2[a]とS2[f indclose(a)]が目的の括弧である. ゆえに, fj ∈west(i)である.
このようにして,面fiの西方向に面fjが隣接するかどうかを調べることができ る. 計算時間はO(1)時間である.
(ea) fj ∈east(i) : 面fiの東方向に面fjが隣接するかどうか ? (wa)と同様である. 略.
次に,面fiの北方向についての隣接クエリの解を求める方法を説明する. この隣 接関係に対応する辺がEN S −EN ST に含まれるときは, S1やS2中には直接格納さ れていないことに注意しよう. いくつかの準備からはじめよう. EN S等の定義につ いては4.1節を参照されたい. DRの点集合を{v1, v2, . . . , vf+3}とする. v1は北面 に対応しTN Sの根である.
はじめに, S2中の括弧の入れ子構造は, 双対グラフDR中の領域の包含関係に対 応することを示す.
4.3. 隣接クエリ 51 各辺e = (vi, vk)∈EEW に対して, DRの領域R(vi, vk)を次のように割りあてよ う. TN S上の, viからv1へのパスをPiとし,vkからv1へのパスをPkとする. Piと Pkと辺eによって囲まれる面からなる領域をR(vi, vk)としよう. DRは平面グラ フであるので, 任意の2つの領域R(vi, vk)とR(vj, vl)が与えられたとき, どちらか 一方がもう一方の一部分のみを真に含むことはない. 次の補題がいえる.
補題 4.3.1 R(vi, vk)がR(vj, vl)を真に含むための必要十分条件は, 辺(vi, vk)に対 応する‘[’と‘]’の組の内側に, 辺(vj, vl)に対応する‘[’と‘]’の組が存在すること である.
証明.
一般性を失うことなくi < j, k < lとする.
(⇒)
背理法による.
辺(vi, vk)に対応するS2中の‘[’と‘]’が辺(vj, vl)に対応するS2中の‘[’と‘]’を 含まないと仮定する.
R(vi, vk)はR(vj, vl)を含むので, 4点vi, vj, vk, vlのpreorderはi < j < l < kで ある.
次の2つの場合にわけて考えよう.
場合1: 辺(vj, vl)に対応する‘[’が辺(vi, vk)に対応する‘[’よりも先に現れる.
辺(vj, vl)に対応する‘[’と‘]’が, 辺(vi, vk)に対応する‘[’と‘]’を含むか, 両者は独立になっているかのどちらかである. どちらの場合も, S1 上で f indclose(select(j)) < f indclose(select(i))であり, かつ, preorderがi < j なのでS1上でselect(i)< select(j)である. よって,viに対応するS1の‘(’と
‘)’は, vjに対応するS1の‘(’と‘)’を含んでいる. ゆえに, TN Sにおいてvjは viの子孫である. これは, R(vi, vk)がR(vj, vl)を含むことに矛盾.
場合2: 辺(vj, vl)に対応する‘[’が, 辺(vi, vk)に対応する‘[’より後に現れる.
このとき, i < k < j < lである. よって, 点vkに対応するS1中の‘(’は, 点 vlに対応するS1中の‘(’よりも先に現れる. これは, l < kであることに矛盾 する.
(⇐)
背理法による. R(vi, vk)はR(vj, vl)を含まないとする.
辺(vi, vk)に対応する‘[’と‘]’は,辺(vj, vl)に対応する‘[’と‘]’を含む. これら に対応するS1中の括弧よりi < l < kである.
次の2つの場合に分けて考えよう.
52 第4章 クエリをサポートする方形描画の符号 場合1: R(vj, vl)がR(vi, vk)を含むとき.
4点vi, vj, vk, vlのpreorderはj < i < k < lである. これはi < l < kである ことに矛盾である.
場合2: 場合1でないとき.
2つの領域R(vi, vk)とR(vj, vl)とは共通部分をもたない. ゆえに, 4点の preorderはi < k < j < lか, j < l < i < kかのどちらかである. どちらの場 合も,i < l < kに矛盾する.
以上により, 主張が正しいことを示せた.
Q.E.D. さて, fiの北方向の親でない隣接面fjについて考えよう. k =fEN(i)とし, これ に対応する点をvkとする. このとき, fi の右上隅の点vがn-missingかe-missing であるかによって2つの場合がある. (図4.10参照.) 点v が(i) n-missingならば l = fW S(j)とし(図4.10(a)参照), (ii) e-missingならばl = fES(j)としよう. (図 4.10(b)参照.) この面に対応する点をvlとする. 辺(vi, vk)と辺(vj, vl)はともに東 西方向の隣接関係に対応している. このとき,また,このときのみ,辺(vi, vk)に対応 する‘[’と‘]’が辺(vj, vl)に対応する‘[’と‘]’をencloseするならば, 領域R(vi, vk) から辺(vi, vk)を輪郭上にもつ面を削除して得られる領域は辺(vj, vl)を外周上に含 むことに注意しよう.
次がいえる.
補題 4.3.2 fi の親面でない面fj が面fiの北方向に隣接するための必要十分条件 は, 辺(vi, vk)に対応する‘[’と‘]’が辺(vj, vl)に対応する‘[’と‘]’をencloseする ことである. (図4.10参照.)
証明.
(⇒)
fjはfiの北方向に隣接するので,領域R(vi, vk)は,領域R(vj, vl)を包含する. (図 4.10参照.) このとき, (vi, vk)に対応する‘[’と‘]’は(vj, vl)に対応する‘[’と‘]’を 包含する. さらに, R(vi, vk)から辺(vi, vk)を輪郭上にもつ面を削除すると,外周上 に(vj, vl)があらわれる. ゆえに, (vi, vk)に対応する‘[’と‘]’は(vj, vl)に対応する
‘[’と‘]’をencloseする.
(⇐)
(vi, vk)に対応する‘[’と‘]’は(vj, vl)に対応する‘[’と‘]’をencloseするので,領 域R(vi, vk)から辺(vi, vk)を輪郭上にもつ面を削除すると,外周上に(vj, vl)があら
4.3. 隣接クエリ 53
vj
vi
vk vj vl
vl
v v
(b) v: e-missing (a) v: n-missing
vi
vk
図 4.10: fiの北方向の隣接面の様子
われる. このとき, 図4.10に示すように, fj はfiの北側に隣接する. 辺(vi, vk)と (vj, vl)はともに東西方向の隣接関係に対応していることに注意しよう.
Q.E.D.
補題4.3.2より, 次のようにして面fiの北方向についての隣接クエリの解を求め
ることができる.
(na) fj ∈north(i) : 面fiの北方向に面fjが隣接するかどうか ? 次の2つの場合に分けて考える.
場合1: fjがfiの親面のとき.
fj ∈north(i)である. enclose命令により,fjがfiの親面になっているかどうか をO(1)時間で計算できることに注意しよう.
場合2: 場合1でないとき.
補題4.3.2より, 辺(vi, vk)に対応するS20 中の‘[’と‘]’が, 辺(vj, vl)に対応する S20 中の‘[’と‘]’を,encloseするときのみfj ∈north(i)である. fiの右上隅の点を vとし,vによって次の2つの場合に分けて考える. S1上でa=f indclose(select(i)) とする. ここで, aは, viに対応するS1中の‘)’を示している.
場合2(a) vがn-missingであるとき. (図4.10(a)参照.)
このとき, l=fW S(j)である. S1中でb=select(j)とすると,S2中で enclose(select(b−3)−1) =select(a−3)−1
54 第4章 クエリをサポートする方形描画の符号 となるときのみfj ∈north(i)である. ここで,select(b−4)は|west(j)|個の
‘]’のうち最初の‘]’を示しているので,select(b−3)は|west(j)|個の‘]’の符 号の“次の”文字を示している. よって, select(b−3)−1は|west(j)|個の‘]’
の符号中の最後の‘]’を示しており, これは辺(vj, vl)に対応することに注意 されたい.
場合2(b) vがe-missingであるとき(図4.10(b)参照.)
このとき,l =fES(j)である. 場合2(a)と同様に,S1中でc=f indclose(select (j))とすると,S2中で
enclose(select(c−4)) =select(a−3)−1 となるときのみfj ∈north(i)である.
最後に, 面fiの南方向についての隣接クエリの解を求める方法を説明する.
(sa) fj ∈south(i) : 面fiの南方向に面fjが隣接するかどうか ?
fiがfjの北側に隣接するとき, またこのときに限り, fj はfiの南側に隣接する.
よって, (nd) により,fjがfiの南側に隣接するかどうかを調べることができる.