Extended Cell Splitting Algorithm の効果的な実装
7
0
0
全文
(2) algorithm ExtendedCellSplit(G , φ , d) input: G : the incidence graph of a cell φ : the equation of a hyperplane h to split with d: the dimension of space output: incidence graph split by a hyperplane 1. calculate either ＋ , − , or 0 for each 0-cell in G using φ 2. for ea ch 1-cell σ in G 3. if σ does not intersect with h 4. t h en compute the position of σ according to h 5. else split_node() 6. for ea ch 2-cell σ in G 7. if σ does not intersect with h 8. t h en compute the position of σ according to h 9. else split_node() 10.for j ← 3 t o dim(G ) 11. for ea ch j-cell σ in G 12. if σ does not intersect with h 13. t h en compute the position of σ according to h 14. else split_node(). 図 ３ ： 2-cell の 線 形 制 約 に よ る 定 義 例. 図 １ ： ア ル ゴ リ ズ ム ext en d ed cell sp lit t in g a lgor it h m. 図 ４ ： cell と そ の in cid en ce gr a p h G (σ 2 1 ). algorithm split_node(G ' , σ , j) input: G ' : the halfway graph of a cell σ : the cell in G which is split by h j: the dimension of s output: the halfway graph which contain two split cells of σ. σ. 1. make new j-cells σ ＋ and σ − in G ' 2. connect σ ＋ and σ − with the (j+1)-cell whose boundary cell is σ 3. for ea ch boundary (j-1)-cell σ ' of σ 4. if the position of σ ' according to h is ＋ (− ) 5. t h en connect σ ' with σ ＋ (σ − ) by an arc in G ' 6. make new (j-1)-cell σ 0 in G ' and set the position according to h as 0 7. connect σ 0 with σ ＋ and σ − by an arc 8. if j>1 9. for ea ch boundar y (j-2)-cell σ 2 of if σ 2 has the position 0 to h t h en connect σ 0 and σ 2 by an arc in G ' 12.remove σ from G ' 図 ２ ： ア ル ゴ リ ズ ム sp lit _n od e 10. 11.. に 導 入 さ れ た ． こ れ ら の complex は ， ど ち ら も 有 界 な cell の 集 合 で あ る ． こ の 為 ， こ の ア ル ゴ リ ズ ム に よ っ て 分 割 さ れ る の は 有 界 cell の み で ある．また，このアルゴリズムを３次元以上の cell に 対 し て 適 用 す る と ， 出 力 さ れ る グ ラ フ は incidence graph と は 異 な る 構 造 に な る ． d 次 元 空 間 中 の BSPtree は ， そ の 葉 ノ ー ド が. d-cell を 表 現 す る ． [7]で 提 案 さ れ て い る ア ル ゴ リ ズ ム Partition_Bspt は ， BSPtree と 超 平 面 を 入 力 と し ， 超 平 面 に よ っ て 分 割 さ れ た BSPtree を出力するアルゴリズムである．これにより d-cell の 分 割 が 計 算 で き る ． [7]に お い て は ， 3 次元空間でのアルゴリズムが示されている．3 次 元 空 間 中 の BSPtree に お い て ， 節 は 葉 ノ ー ド が 示 す 3-cell を 隔 て る 2 次 元 多 角 形 で あ る ． こ の 多 角 形 を ，頂 点 の リ ス ト と し て 保 持 し て い る ． ま た ， 空 間 を 十 分 大 き な box で 囲 む こ と で ， 非 有 界 な cell を 含 ま な い よ う に し て い る ．. 3. cell と incidence gr a ph こ の 章 で は ， cell と incidence graph に つ い て の説明をする． d 次 元 ユ ー ク リ ッ ド 空 間 を E d で 表 現 し ，空 間 物 は こ の 中 に 存 在 す る も の と す る ．本 論 文 で は ， cell を σ で 表 現 し ，そ の incidence graph を G (σ ) と 表 記 す る ．E d 中 の 任 意 の 点 を p=(x 1 ，x 2 ，．．．， x d )と す る ．E d 中 の (d-1)次 元 部 分 空 間 で あ る 超 平 面 h j は d+1 個 の 係 数 α j i(1≦ i≦ d+1)に よ り 線 形 式 φ j (p)=α j 1 x 1 +α j 2 x 2 +．．． +α jd x d +α j (d+ 1) を 定 め た 時 ，φ j (p)=0 で 定 義 さ れ る ．op j を 比 較 演 算 子 ≦ ， ≧ ， or =と す る 時 ， "φ j (p) op j 0"は ， 線 形 制 約 を 表 現 す る ． ま た H (σ )を ， σ を 構 成 す る超平面集合とする．. −70−.
(3) algorithm is1-CellIntersect(n, {σ 0 1 ,..,σ 0 n }, h j ) input: n: the number of 0-cell connect with σ 1 1 { σ 0 1 ,..,σ 0 n }: the 0-cells connect with σ 1 1 h: hyperplane to split σ 1 1 output: true or false 1. if n = 2 2. t h en if there aren't both σ 0 i which position according to h is + and− 3. t h en r et u r n false 4. else r et u r n true 5. else if n = 1 6. t h en if a vectorα j =(α j1 , α j2 , ..., α jd ) and a vector v along σ 1 1 satisfy α j ・ v > 0 and σ 0 1 's position is− or α j ・ v < 0 and σ 0 1 's position is＋ or 7. t h en r et u r n true 8. else r et u r n false 9. else 10. if α j ・ v = 0 11. t h en r et u r n true 12. else r et u r n false 図 ５：1cellσ 1 1 が 超 平 面 h j と 交 差 す る か ど う かの判定. 図 ７ ： in cid en ce gr a p h の 実 装. 図 ６ ： 非 有 界 cell の 例. cell σ は 異 な る い く つ か の 線 形 制 約 を 満 足 す る 点 の 集 合 と し て 表 現 さ れ る (図 ３ )． σ を 表 現 す る n 個 の 線 形 制 約 を φ 1 (p) op 1 0∧ φ 2 (p) op 2 0 ∧ ．．．∧ φ n (p) op n 0 と し ，φ j (p)=0 (1≦ j≦ n) で 与 え ら れ る 超 平 面 を ｈ ｊ と す る と H (σ )={h 1 ， h 2 ，．．．， h n }と な る ． cellσ を 定 義 す る 超 平 面 が m 個 の 異 な る 方 程 式 φ j (p)=0 で あ る 場 合 ， σ の 次 元 dim(σ )は d-m で あ る ．本 論 文 で は ，k 次 元 cell を k-cell と 表 現 し σ k と 表 記 す る ．. cell に は ， 有 界 な も の と ， 非 有 界 な も の が あ る ． cell σ の 中 に 任 意 の 二 つ の 点 を と っ た 時 ， それらの距離より大きい実数 r が存在するとき， σは有界である．そうでなければσは非有界で あ る (図 ６ )． k-cell σ k の incidence graph G(σ k ) は ，σ k を 構 成 す る k 次 元 以 下 （ σ k を 含 む ） の cell の 接 続 関 係 を 表 現 す る も の で あ る ． cell は 節 で 表 現 さ れ ， s-cell と (s-1)-cell (1≦ s≦ k)の 接 続 関 係 は 枝で表現される．図４に例を示す．この三角形 は １ つ の 2-cell σ 2 1 ， ３ つ の 1-cell σ 1 1 σ 1 2 σ 1 ３ つ の 0-cellσ 0 1 σ 0 2 σ 0 3 で 構 成 さ れ て い る ． 3， 2-cellσ 2 1 は ３ つ の 1-cellσ 1 1 σ 1 2 σ 1 3 と 接 続 し て い る ．そ の 為 ，そ れ ら を 結 ぶ 枝 が 存 在 す る ． 1 つ の 超 平 面 φ j (p i)＝ 0 と 1 つ の 点 p i =(x i1 ， x i2 ，．．．，x id )が φ j (p i )＞ (＜ or＝ )0 を 満 た す と き ， 点 p i の position は ＋ (− or0)で あ る ． 図 ７ に incidence graph の 実 装 を 示 す ． 0-cell σ 0 1 は ，h 1 ，h 2 ，h 3 そ れ ぞ れ に 対 し て position 0， 0， +を 持 ち ， 座 標 が (1． 0， 3． 0)で あ る の で ， こ れ ら の 情 報 を 節 に 保 存 し て い る ．k-cell(k≧ 1). −71−.
(4) に つ い て は ，超 平 面 集 合 H (σ )に 対 す る position を格納する．. 4. cell の 分 割 この章においては，まず，分割により新たに G (σ )中 に 生 成 さ れ た 節 に 対 し て ，枝 の つ な ぎ 直 しを行うアルゴリズムについて説明する．これ は ， 分 割 結 果 を incidence graph と し て 出 力 す る 為 の も の で あ る ．次 に ，cell splitting algorithm [1] が ， 非 有 界 な cell の 分 割 に 適 用 で き な い 理 由 を 示 し ， extended cell splitting algorithm の 基 本 と なる考えを説明する． 非 有 界 な cell の 場 合 ， そ の incidence graph は 0-cell を 含 む 場 合 と 含 ま な い 場 合 に 分 か れ る ． 0-cell を 含 ま な い の は ，そ の cell が 半 空 間 を 表 すという特別なケースであり，一般的には 0-cell を 含 む と 考 え て よ い ． 我 々 は ， そ の cell が 含 む 0-cell σ 0 の 位 置 ベ ク ト ル の 値 と ，σ 0 に 接 し て い る 1-cell の 方 向 ベ ク ト ル 及 び h の 法 線ベクトルとの内積を取ることで，単に，σの 線 形 多 項 式 と h の 線 形 方 程 式 を 解 く よ り も ，効 率良く交差判定ができることを見出し，実装し た． 4． 1 グ ラ フ の 操 作 超 平 面 h に よ る cell σ の 分 割 は ， σ の incidence graph G (σ )を 入 力 と す る ．分 割 の 結 果 ， 新 し い 節 が incidence graph に で き る ． G (σ ) を構成する種々の節のうち，h と交差するよう な 1 次 元 以 上 の cell を 表 現 す る 節 は 2 つ に 分 割 さ れ ，結 果 と し て 新 し い 3 つ の 節 が で き る（ 元 の 節 は 削 除 さ れ る ）．例 え ば あ る 2 次 元 cell に h が交差しているようなときは，分割の結果，2 次 元 の cell が 新 し く 2 つ で き る と と も に ， こ の cell と h の 積 部 分 を 表 す 1 次 元 の cell が で き る ． こ の 処 理 は ， cell σ と 超 平 面 h と の 交 差 判 定 ， そ れ ら が 交 差 す る 場 合 は σ に 関 す る 新 し い 節 の生成とσの削除，それに伴う枝のつなぎなお し と い う 3 手 順 で 行 わ れ る ．こ の 処 理 は ，有 界・ 非 有 界 ど ち ら の cell に 対 し て も 同 様 で あ る ． σが交差する場合のσに関する新しい節の 生 成 と σ の 削 除 は ， 単 に dim( σ ) 次 元 の cell を 2 個 ， dim(σ )-1 次 元 の cell を 1 個 作 る に 過 ぎ な い の で ， 実 装 は 容 易 で あ る ． 拡 張 cell splitting ア ル ゴ リ ズ ム で は ， incidence graph 内 の cell σ を 超 平 面 h で 分 割 す る と き ， 次 の 手 順を踏む． (1) σ を dim(σ ) 次 元 の ２ つ の cell σ ＋ と σ−に分割し，σと接続する全ての dim(σ )次 元 の cell の 節 と 枝 で つ な ぐ ． ま た ， σ に 接 続 す る dim(σ )-1 次 元 の cell 全 て に つ い て ，そ の position に よ り ， σ＋とσ−のどちらかと枝でつなぐ．. 図 ８ ： 有 界 cell の 超 平 面 に よ る 分 割. (2). (3). (4). h と σ の 交 差 部 分 に あ る dim(σ )-1 次 元 の cell の 節 を 生 成 す る ． こ の cell を σ 0 と す る ．σ 0 と (1)で 作 成 し た σ ＋ とσ−を枝でつなぐ． dim(σ ) > 1 の と き は ，σ 0 の 境 界 上 に あ る dim(σ )− 2 次 元 の cell の う ち h 上 に あ る cell 全 て と σ 0 と を 枝 で つ な ぐ 処 理 を 行 う ．こ う し た cell は ，そ の 時 点 の incidence graph に お い て σ か ら 枝を 2 回辿って，まず，σ0 の境界上 に あ る dim(σ )− 2 次 元 を 得 て ，そ の 後 ， それらの位置ベクトルを使って h 上に あるかを調べることで得られる． 最後に，σを削除する. 以上の手順で， が分割され，新しい節が で き る と と もに ， 枝 の つ な ぎ 直 し が 行 われ る ． 我 々 は ，上 記 の ア ル ゴ リ ズ ム を 図 ２の ように実装した． 但 し ，(2) の 処 理 は ，2 次 元 の cell の 場 合 に は ， 単 純 に 0 と グ ラ フ 内 の j 2 次 元 の cell と を 全 て arc で つ な ぐ と い う 単 純 な 方 式 で も 動 く（ こ れ は ，Chandrajit ら が 示 し た 実 装 法 ）．し かし，3 次元以上では動かない．我々が上記に 示したアルゴリズムは，グラフの節に持たせた H (σ )に 対 す る position を 使 い ，グ ラ フ 内 の j 2 次 元 の cell で し か も ，h 上 に あ る も の を 選 ぶ と ]. −72−.
(5) 割 さ れ る と 判 定 さ れ る ． こ の 場 合 も ， 1-cell の 場合と同様に節の作成，枝のつなぎ直しの処理 が行われる． [1]に 示 さ れ て い る ア ル ゴ リ ズ ム で は ，非 有 界 な 1-cell の 分 割 判 定 を 正 し く 行 う こ と が で き な い．このアルゴリズムを適用する為には，全て の 1-cell が 二 つ の 0-cell に 接 続 し て い る 必 要 が あ る 為 で あ る ． し か し 非 有 界 な cell は ， こ の 条 件を満足しない．例えば，半直線は１つの点に のみ接続し，直線は点に接続しない．. 図 ９ ： 非 有 界 な 1-cell の 例 (a ) 端 点 を 一 つ も つ 1-cell (b ) 端 点 を 持 た な い 1-cell いう方式をとっており，3 次元以上の任意の次 元で正しく動く． 図 8 に 例 を 示 す ． (a)の σ 1 2 ， σ 1 3 に 対 し て 分 割 処 理 を 行 っ た 結 果 が (b)で あ る ．さ ら に σ 2 1 の 分 割 処 理 を 行 っ た 結 果 が (c)で あ る ．図 8(b)の よ う に ， 全 て の cell に 対 し て 分 割 処 理 を 終 え て い な い 時 点 の グ ラ フ は ， incidence graph と は 異 な る構造になっている．. 4． 2 有 界 な 1-cell の 分 割 Candrajit ら の cell splitting algorithm[1] は ， 0-cell の position を 利 用 し て 1-cell（ 線 分 ） が 超 平面によって分割されるかどうかを判定する． ま ず 始 め に ， 2 つ の 0-cell に つ い て 超 平 面 に 対 す る position を 計 算 す る ．そ し て ，２ つ の 0-cell の position か ら ，1-cell が 分 割 さ れ る か ど う か を 判 定 す る ． も し ， ２ つ の position が ＋ と − で あ れ ば ， 1-cell は 分 割 さ れ る ． そ う で な け れ ば ， 分 割 さ れ な い ． こ の 時 ， 2 つ の 0-cell が ど ち ら も 0 で あ れ ば ，1-cell は 0 で あ る ．0-cell が ど ち ら も ＋ (− )，又 は ＋ と 0（ − と 0）で あ れ ば ，1-cell は＋（−）である． 例 え ば ， 図 ８ に お い て ， ３ つ の 0-cell σ 0 1 ， σ 0 2 ，σ 0 3 の position は ，そ れ ぞ れ ＋ ，− ，＋ で あ る ．1-cell σ 1 1 は ２ つ の 0-cell σ 0 1 ，σ 0 3 に 接 続 し て い る が ， 両 方 と も position は − で あ る ． よ っ て ，σ 1 1 も − と 判 定 さ れ る ．ま た ，1-cell σ 1 1 2 と σ 3 は ＋ と − の 0-cell に 接 続 し て い る 為 ， 超平面 h により分割されると判定される． 1-cell が 超 平 面 に よ り 分 割 さ れ る と 判 定 さ れ る と ，G (σ )に 新 た な 節 を 作 成 し ，枝 の つ な ぎ 直 す 処 理 が 行 わ れ る ． 例 え ば ， 1-cell が 分 割 さ れ る 場 合 ， ２ つ の 1-cell と ， そ の 間 に あ る 0-cell が 新 た に 生 成 さ れ ，も と の 1-cell は 削 除 さ れ る ． また，これらの節に対して枝のつなぎ直しが行 わ れ る ． こ の よ う に し て ， 全 て の 1-cell に つ い て ， 処 理 が 終 了 し た 後 ， k-cell(k ≧ 2) に つ い て ， 処 理 が 繰 り 返 さ れ る ． k-cell が 分 割 さ れ る か 否 か の 判 定 は ， k-cell に 接 続 す る (k-1)-cell の position か ら 判 定 す る ． (k-1)-cell の position に ＋ と − が 両 方 含 ま れ て い る 場 合 は ， k-cell は 分. 4． 3 ext en d ed cell sp lit t in g a lgor it h m extended cell splitting algorithm は ，２ つ の 点 の position を 利 用 し て ，1-cell が 超 平 面 に よ り 分 割 さ れ る か ど う か を 判 定 す る ． 1-cell が 有 界 で あ る 場 合 は ， ２ つ の 端 点 の position を 利 用 す る ． 1-cell が 非 有 界 で 端 点 を 一 つ だ け 持 つ 場 合 は ， そ の 端 点 と ， 1-cell 上 に あ り 端 点 か ら 十 分 離 れ た 所 に あ る 点 の position を 利 用 す る (図 ９ (a))． 1-cell が 端 点 を 持 た な い 場 合 は ，1-cell 上 に あ り ， 互 い に 十 分 離 れ た ２ つ の 点 の position を 利 用 す る (図 ９ (b))． こ れ ら の 点 の position は ， 次 の よ う に し て 求 めることができる．l を任意の直線とする．図 10 に ３ r次 元 空 間 で の 例 を 示 す ． 図 r10 に 示 す よ うに， v は l に沿ったベクトル， u は，原点か ら l への垂線の足の点 q を表すベクトルとする． r p ( x1 , x2 ,..., xd ) rを l 上 r の点 r p を表す d 次元ベ ク ト ル と す る と ， p は v ， u と ２ 点 q， p の 距 離を示す t を用いて次のように表現される．. −73−. r p. r r tv u. こ こ で ， 超 平 面 hi の 垂 直 ベ ク ト ル. r. (. j1. ,. j2. ,...,. jd. r. ) を 用 い て ' j ( p) を 次 の. ように定める．. r ' j ( p) この時，. r j. r v r v r v. j. r j. r p. j ( d 1). r r ' j ( p) で あ り ，ベ ク ト ル v と. ( p). は次のような性質を持つ．. r j. 0. j. 0. j. 0. r r. r lim ' j ( p) t r lim ' j ( p) t r lim ' j ( p) t. r j. r u. j ( d 1).
(6) 図１０：３次元空間の直線 l. 4． 4 半 直 線 の 超 平 面 に よ る 分 割 半 直 線 の 場 合 は ， 端 点 の position は ， 接 続 0-cell の 座 標 と 超 平 面 に よ り 求 め ら れ る ． そ し て ， も う １ つ は ， 半 直 線 上 に あ り ， 0-cell か ら 十 分 離 れ た 所 に あ る 点 の position を 利 用 す る ． こ の 点 の position は 4．2 章 で 示 し た 方 法 で 求 め ることができる．そして，求まった２つの position か ら ，1-cell が 超 平 面 に よ り 分 割 さ れ る かどうかを判定する． 図 11 は 簡 単 の た め ，２ 次 元 空 間 で の 例 を 示 す ． 図 11(a) に お い て ， 0-cell σ 0 1 の h 1 に 対 す る position は ＋ で あ る ． 次 に ，. r 1. r p. (1, 3) (0.2, 0.15) 0.45 0. よ り ， p の position は ＋ と 判 定 さ れ る ． よ っ て ２ 点 の position が ど ち ら も ＋ で あ る の で ， σ 1 1 は ＋ で あ る ． 図 １ １ (b)に お い て も ， σ 0 1 は h 2 に対して＋である．次に. r r. 2 2. r p ( 3, 4) (0.2, 0.15) 0 r u ( 3, 4) ( 0.12, 0.16) 23. 2 3 0. よ り ， p の position は ＋ と 判 定 さ れ る ． よ っ て こ の 場 合 も ， ２ 点 の position が ど ち ら も ＋ で あ る の で ，σ 1 1 は ＋ で あ る ．図 １ １ (c)に お い て は ， σ 01 は h 3 に 対 し て − で あ る ． そ し て. r 1. r p. (1, 3) (0.2, 0.15) 0.45 0. よ り ，p の position は ＋ で あ る ．２ 点 の position が ＋ と − で あ る の で ， σ 11 は 分 割 さ れ る ．. 図 １ １ ： 端 点 を 一 つ 持 つ 1-cellσ 0 1 の. 超平面による分割 5. 性 能 テ ス ト 我 々 は ， extended cell splitting algorithm を 実 装 し ， 性 能 テ ス ト を 行 っ た (図 １ ２ )． こ の テ ス ト で は ， 入 力 と し て 空 間 次 元 d と cell の 分 割 に 用 い る 超 平 面 数 N h が 与 え ら れ る ．ま ず ，d 個 の 超 平 面 で 構 成 さ れ る d 次 元 非 有 界 cell を 作 成 す る ．そ し て ，こ の cell を ラ ン ダ ム に 作 成 し た N h 個の超平面で繰り返し分割し，それに要した時 間 を 測 定 し た ． cell の 集 合 を 一 つ の 超 平 面 で 分 割する処理は，次のように行う．まず，全ての 0-cell の position を 計 算 す る ．そ し て ，4 章 で 示 し た 方 法 で ， 全 て の 1-cell に つ い て ， 超 平 面 に よ り 分 割 さ れ る か ど う か を 判 定 し て い く ．k-cell (2≦ k≦ d) に つ い て は ，[1]と 同 様 の 方 法 で 分 割 さ れ る か ど う か を 判 定 す る ． incidence graph の 操作は図１，図２に示した通りである． 上 記 の テ ス ト を d=3， 1≦ N h ≦ 20 に つ い て 行 っ た ． 結 果 を 図 １ ２ に 示 す ． 横 軸 は ， k-cell (0 ≦ k≦ 3)の 総 数 で あ り ，縦 軸 は 分 割 に 要 し た 時 間 で あ る ． 環 境 は Sun Blade 100， 512MB メ モ リ ， OS は SunOS 5． 10 で あ る ．. −74−.
(7) 図１２：性能テストの結果. 6. ま と め 本 論 文 で は ， 非 有 界 な 1-cell が 超 平 面 に よ り 分 割 さ れ る か ど う か の 判 定 法 を 示 し た ． 1-cell は ， そ の 上 に あ る ２ 点 の position を 求 め ， そ れ らを利用することで超平面により分割されるか どうかを判定することができた．次に 3 次元以 上 の cell に 対 し て も ，分 割 結 果 を incidence graph として出力するアルゴリズムを示した．また， 上 記 を 実 装 し ，そ の 性 能 テ ス ト の 結 果 を 示 し た ．. [6] Jacob E ． Goodman ， Joseph O’Rourke ， Handbook of discrete and computational geometry， CRC Press ， 2004． [7] Bruce Naylor， John Amanatides， William Thibault ， " Merging BSP trees yields pol yhedral set operations" ， ACM SIGGRAPH Computer Graphics ， Proceedings of the 17th annual conference on Computer graphics and interactive techniques， Volume 24 Issue 4， September 1990 [8] Michiko Tanaka ， Kunihiko Kaneko ， Yingliang Lu， Akifumi Makinouchi， “An Extended Cell Splitting Algorithm for Spatial Databases ， ” IEEE TENCON 2004 ， p ． 371-374， November 2004 [9] Yingliang Lu， Kunihiko Kaneko， Akifumi Makinouchi， Michiko Tanaka， “Reducing the Data Size of Spatial Databases Using Sign Vectors， ” IEEE TENCON 2004， p． 367-370， November 2004 [10] Yves Nievergelt， "Analysis and applications of Priest's distillation"， ACM Transactions on Mathematical Software (TOMS)， Volume 30 Issue 4， December 2004. 7. 謝 辞 本研究の一部は，日本学術振興会科学研究費補 助 金 課 題 番 号 17700117 ， (A)(2)16200005 に よ る．. 文. 献. [1] Chandrajit L． Bajaj and Valerio Pascucci， “Splitting a Complex of Convex Pol ytopes In Any Dimension，” ACM Press， proceedings of the twelfth annual symposium on computational geometry， pp88-97， 1996． [2] S． Nirenstein， E． Blake， J． Gain， “Exact from-region visibility culling， ” Proceedings of the 13th Eurographics workshop on Rendering， June 26-28， 2002， Pisa， Italy [3] Herbert Edelsbrunner ， Algorithms in Combinatorial Geometry， Springer-Verlag， 1987． [4] H． Edelsbrunner， R． Seidel， M．Sharir， “On the Zone Theorem for Hyperplane Arrangements” ， SIAM jurnal on Computing， Volume 22Issue 2， pages 418 429， 1993 [5] M．de Berg， M．van Kreveld， M．Overmars， O． Schwarzkopf， Computational Geometry Algorithms and Applications ， Springer ， 1998. −75−.
(8)
図
+2
関連したドキュメント
Associate Professor, Graduate School of Marine Science and Technology, Tokyo University of Marine Science and Technology (Ocean Newsletter No. Designation of the Takashima Kozaki
Department of Cardiovascular and Internal Medicine, Kanazawa University Graduate School of Medicine, Kanazawa (N.F., T.Y., M. Kawashiri, K.H., M.Y.); Department of Pediatrics,
3 Department of Respiratory Medicine, Cellular Transplantation Biology, Graduate School of Medicine, Kanazawa University, Japan. Reprints : Asao Sakai, Respiratory Medicine,
＊2 Kanazawa University, Institute of Science and Engineering, Faculty of Geosciences and civil Engineering, Associate Professor. ＊3 Kanazawa University, Graduate School of
* Department of Mathematical Science, School of Fundamental Science and Engineering, Waseda University, 3‐4‐1 Okubo, Shinjuku, Tokyo 169‐8555, Japan... \mathrm{e}
French case system has a case called tonic in addition to nominative, accusative and dative, and all French nominal SFs appear in tonic forms, regardless of what case their
The purpose of the Graduate School of Humanities program in Japanese Humanities is to help students acquire expertise in the field of humanities, including sufficient
