https://orsj-ml.org/orwiki/wiki/index.php?action=history&feed=atom&title=%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E6%B3%95
バケット法 - 版の履歴
2026-04-09T21:12:03Z
このウィキのこのページに関する変更履歴
MediaWiki 1.35.3
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E6%B3%95&diff=9702&oldid=prev
Imahori: 基礎編と用語編のマージ
2008-03-13T14:25:55Z
<p>基礎編と用語編のマージ</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2008年3月13日 (木) 14:25時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >1行目:</td>
<td colspan="2" class="diff-lineno">1行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''【ばけっとほう (bucket method)】'''</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>'''【ばけっとほう (bucket method)】'''</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">=== 概要 ===</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>幾何的な問題をより単純に高速に処理するための実際的方法である. 対象物が2次元の<math>n\,</math>点からなる図形のときは, 対象物を座標軸に平行な辺からなる長方形で覆い, それを縦横<math>\lceil\sqrt{n}\ \rceil\,</math>等分し全部で<math>\Theta(n)=\lceil\sqrt{n}\ \rceil \times \lceil\sqrt{n}\ \rceil\,</math>個のバケットと呼ばれる小長方形領域に分割して図形を各バケットで切り出し管理する. すると問題を各バケット内での極めて単純な問題に帰着できることもしばしばあり, 高速に処理できることになる.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>幾何的な問題をより単純に高速に処理するための実際的方法である. 対象物が2次元の<math>n\,</math>点からなる図形のときは, 対象物を座標軸に平行な辺からなる長方形で覆い, それを縦横<math>\lceil\sqrt{n}\ \rceil\,</math>等分し全部で<math>\Theta(n)=\lceil\sqrt{n}\ \rceil \times \lceil\sqrt{n}\ \rceil\,</math>個のバケットと呼ばれる小長方形領域に分割して図形を各バケットで切り出し管理する. すると問題を各バケット内での極めて単純な問題に帰着できることもしばしばあり, 高速に処理できることになる.</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del class="diffchange diffchange-inline">詳しくは</del>[[<del class="diffchange diffchange-inline">《バケット法》</del>|<del class="diffchange diffchange-inline">基礎編：バケット法</del>]]<del class="diffchange diffchange-inline">を参照.</del></div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">=== 詳説 ===</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 計算幾何の実用的なアルゴリズムの代表的設計法の一つであり, 平面最小重み完全</ins>[[<ins class="diffchange diffchange-inline">マッチング]] (matching), [[点位置決定]] (point location) などが[[バケット法]] (bucket method) に基づいて効率的に解かれている. 簡単のため2次元で説明するが, 高次元にも容易に一般化できる. 平面上にサイズ<math>n\, </math>の解きたい問題が与えられたとする. 問題を含む領域を軸に平行な辺からなる長方形で覆い, 軸に垂直な直線を引いて<math>\Theta(n)\, </math>個のバケットと呼ばれる合同な小長方形に分割する. そして全体の問題をそれぞれのバケット内の問題として分割して記憶する. すると通常はバケット内での問題だけで全体の解が得られるので高速になる. バケット間にまたがる情報を必要に応じて利用しなければならない場合もあるがこの場合も高速な手法があることが多い. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 具体例でより詳しく説明する. 与えられた平面上の<math>n=2m\, </math>個の点集合に対して, <math>2\, </math>点ずつペアにして<math>m\, \, </math>個のペアの集合<math>M\, </math>をつくるという問題を考える. このような<math>M\, </math>は, 完全マッチングと呼ばれている. その際, ペアの重みをそのペアに含まれる<math>2\, </math>点間の距離(<math>2\, </math>点を結ぶ線分の長さ)とする. 完全マッチング<math>M\, </math>の重みを<math>M\, </math>に含まれる<math>m\, </math>個のペアの重みの総和と見なし, 重みを最小にする完全マッチングを求める問題を平面最小重み完全マッチングというが, この問題をバケット法に基づいて解決しその実用性を実証した研究 [2] が, 計算幾何学の問題に対するバケット法の最初の適用例といわれている. できるだけ小さい重みの完全マッチングをつくるわけであるので, 遠く離れた<math>2\, </math>点がペアになる可能性は低い. そこで, 対象領域(長方形領域)を縦横<math>\lceil \sqrt{n}\ \rceil\, </math>等分し全部で<math>\lceil \sqrt{n} \ \rceil \times \lceil \sqrt{n} \ \rceil=\Theta(n)\, </math>個のバケットに分割して, 同一のバケットに含まれる点でまずペアをつくる. 最小重みの完全マッチングには距離の小さい<math>2\, </math>点がペアとして含まれることが多いので, 同一のバケットに含まれるもの同士をペアにするということは, 同一のバケットに含まれる2点は極めて近い点である可能性が高く, 異なるバケットに属する2点は遠くにある可能性が高いという, 自然な仮定に基づいている. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> このように, バケット法では問題を局所領域に限定できるという特徴がある. さらに, 与えられる点の集合が対象領域において一様に分布するときは, <math>n=2m\, </math>個の点に対してほぼ同数個のバケットに分割しているので, 各バケットは平均的に一定数(<math>\mbox{O}(1)\, </math>)個の点しか含まないといえる. したがって, 各バケット内での最小重み完全マッチングは<math>\mbox{O}(1)\, </math>の手間で見つけることができる. このように, バケット法では, バケット内の問題が極めて単純であるという特徴も併せもっている. さらに, バケットは合同な長方形であるため, バケットに含まれる点も簡単に求められるという特徴もある. このような特徴から, バケット法に基づく手法は, 一般に極めて高速となる [1]. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 上の平面最小重み完全マッチングの問題では, バケット内での完全マッチングだけでは, 全体の完全マッチングとはならずに, ペアにされていない点が残るのが普通で, 最終的には, バケット間にまたがる点同士でさらにペアをつくっていかなければならないが, これは, <math>2\, </math>次元バケット間の距離を, ある程度忠実に保存するようにして, 一列に並べ, その順番で次々とペアにしていけばよい. このようにして求められた完全マッチングは, 最小重みの完全マッチングでないことが多いが, 詳細な解析により, かなり精度の高い解となることが保証されている [2]. 最適解はネットワークのアルゴリズムを用いて<math>\mbox{O}(n^3)\, </math>の手間で解けるが, 上記のバケット法に基づく方法は<math>\mbox{O}(n)\, </math>の手間であり, 実際の応用では極めて有効である. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> 平面最小重み完全マッチングをプロッターでペンを用いて地図を描く際の筆順最適化 (optimal drawing (of map) ) に応用する. 地図をきれいに描くため, 同じ線を<math>2\, </math>度描くことはしないものとする. ペンをおろして線を描いているときもあるし, ペンを上げて次に描くべき線の始まりまで移動しているときもある. 地図を描くという観点からすると, ペンをおろして線を描くという動作は必要不可欠なものである. これに対して, ペンを上げて次に描くべき線の始まりまで移動する動作は, 空送りと呼ばれ無駄な動作であるので, できるだけ少なくするのがよい. さて, 地図が一筆書き可能なら空送りをすることなく描けることになる. 地図が一筆書き不可能ならば空送りの部分に対応する線を付け加えた図で一筆書きできるように変形して描くことになる. プロッターでの描画に要する時間は, ほぼ, この<math>2\, </math>つの動作に要する時間の総和になるので, 描画時間を減らすには, 空送り全体に要する時間を減らせばよい. これらの動作に要する時間は移動量に比例するものとすれば, 空送り全体の移動量(移動距離)を最小にすれば, 描画に要する時間は最小ということになる. これは平面最小重み完全マッチングに帰着できる. 地図が一筆書き不可能ならば奇数本の線が接続する点を全部拾ってきて(すると点は偶数個になる), <math>2\, </math>個ずつペアにして完全マッチングを求め, 完全マッチングに含まれる線を空送りに対応させて付け加えれば一筆書きできることになる. 完全マッチングの選び方により付け加えた線の総長は異なるので, 総長最小の完全マッチングを求める問題となる. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline"> その他の計算幾何の様々な探索問題に対するバケット法の応用については文献 [1, 3] を参照のこと. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">----</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">'''参考文献'''</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[1] T. Asano, M. Edahiro, H. Imai, M. Iri and K. Murota, "Practical Use of Bucketing Techniques in Computational Geometry," in ''Computational Geometry'', G.T. Toussaint, ed., North-Holland, 1985.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[2] M. Iri, K. Murota and S. Matsui, "Heurisitics for Planar Minimum Weight Perfect Matchings," ''Networks'', '''13''' (1983), 67-92. </ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[3] 伊理正夫監修, 腰塚武志編集, 『計算幾何学と地理情報処理(第２版)』, 共立出版, 1993.</ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[[Category:計算幾何</ins>|<ins class="diffchange diffchange-inline">ばけっとほう</ins>]]</div></td></tr>
</table>
Imahori
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E6%B3%95&diff=8349&oldid=prev
2007年8月8日 (水) 12:12にKanda.kによる
2007-08-08T12:12:09Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2007年8月8日 (水) 12:12時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l2" >2行目:</td>
<td colspan="2" class="diff-lineno">2行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>幾何的な問題をより単純に高速に処理するための実際的方法である. 対象物が2次元の<math>n\,</math>点からなる図形のときは, 対象物を座標軸に平行な辺からなる長方形で覆い, それを縦横<math>\lceil\sqrt{n}\ \rceil\,</math>等分し全部で<math>\Theta(n)=\lceil\sqrt{n}\ \rceil \times \lceil\sqrt{n}\ \rceil\,</math>個のバケットと呼ばれる小長方形領域に分割して図形を各バケットで切り出し管理する. すると問題を各バケット内での極めて単純な問題に帰着できることもしばしばあり, 高速に処理できることになる.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>幾何的な問題をより単純に高速に処理するための実際的方法である. 対象物が2次元の<math>n\,</math>点からなる図形のときは, 対象物を座標軸に平行な辺からなる長方形で覆い, それを縦横<math>\lceil\sqrt{n}\ \rceil\,</math>等分し全部で<math>\Theta(n)=\lceil\sqrt{n}\ \rceil \times \lceil\sqrt{n}\ \rceil\,</math>個のバケットと呼ばれる小長方形領域に分割して図形を各バケットで切り出し管理する. すると問題を各バケット内での極めて単純な問題に帰着できることもしばしばあり, 高速に処理できることになる.</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;"></ins></div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">詳しくは[[《バケット法》|基礎編：バケット法]]を参照.</ins></div></td></tr>
</table>
Kanda.k
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E6%B3%95&diff=6738&oldid=prev
Orsjwiki: "バケット法" を保護しました。 [edit=sysop:move=sysop]
2007-07-20T01:26:03Z
<p>"バケット法" を保護しました。 [edit=sysop:move=sysop]</p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<tr class="diff-title" lang="ja">
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="1" style="background-color: #fff; color: #202122; text-align: center;">2007年7月20日 (金) 01:26時点における版</td>
</tr><tr><td colspan="2" class="diff-notice" lang="ja"><div class="mw-diff-empty">(相違点なし)</div>
</td></tr></table>
Orsjwiki
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E6%B3%95&diff=5369&oldid=prev
2007年7月17日 (火) 06:53に122.17.2.240による
2007-07-17T06:53:47Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2007年7月17日 (火) 06:53時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >1行目:</td>
<td colspan="2" class="diff-lineno">1行目:</td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>【ばけっとほう (bucket method)】</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">'''</ins>【ばけっとほう (bucket method)】<ins class="diffchange diffchange-inline">'''</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>幾何的な問題をより単純に高速に処理するための実際的方法である. 対象物が2次元の<math>n\,</math>点からなる図形のときは, 対象物を座標軸に平行な辺からなる長方形で覆い, それを縦横<math>\lceil\sqrt{n}\ \rceil\,</math>等分し全部で<math>\Theta(n)=\lceil\sqrt{n}\ \rceil \times \lceil\sqrt{n}\ \rceil\,</math>個のバケットと呼ばれる小長方形領域に分割して図形を各バケットで切り出し管理する. すると問題を各バケット内での極めて単純な問題に帰着できることもしばしばあり, 高速に処理できることになる.</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>幾何的な問題をより単純に高速に処理するための実際的方法である. 対象物が2次元の<math>n\,</math>点からなる図形のときは, 対象物を座標軸に平行な辺からなる長方形で覆い, それを縦横<math>\lceil\sqrt{n}\ \rceil\,</math>等分し全部で<math>\Theta(n)=\lceil\sqrt{n}\ \rceil \times \lceil\sqrt{n}\ \rceil\,</math>個のバケットと呼ばれる小長方形領域に分割して図形を各バケットで切り出し管理する. すると問題を各バケット内での極めて単純な問題に帰着できることもしばしばあり, 高速に処理できることになる.</div></td></tr>
</table>
122.17.2.240
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E6%B3%95&diff=3893&oldid=prev
2007年7月12日 (木) 18:49に211.9.162.254による
2007-07-12T18:49:46Z
<p></p>
<table class="diff diff-contentalign-left diff-editfont-monospace" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="ja">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← 古い版</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">2007年7月12日 (木) 18:49時点における版</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >1行目:</td>
<td colspan="2" class="diff-lineno">1行目:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>【ばけっとほう (bucket method)】</div></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>【ばけっとほう (bucket method)】</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>幾何的な問題をより単純に高速に処理するための実際的方法である. 対象物が2次元の<del class="diffchange diffchange-inline">$</del>n<del class="diffchange diffchange-inline">$</del>点からなる図形のときは, 対象物を座標軸に平行な辺からなる長方形で覆い, それを縦横<del class="diffchange diffchange-inline">$</del>\lceil\sqrt{n}\ \rceil<del class="diffchange diffchange-inline">$</del>等分し全部で<del class="diffchange diffchange-inline">$</del>\Theta(n)=\lceil\sqrt{n}\ \rceil \times \lceil\sqrt{n}\ \rceil<del class="diffchange diffchange-inline">$</del>個のバケットと呼ばれる小長方形領域に分割して図形を各バケットで切り出し管理する. すると問題を各バケット内での極めて単純な問題に帰着できることもしばしばあり, 高速に処理できることになる.</div></td><td class='diff-marker'>+</td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>幾何的な問題をより単純に高速に処理するための実際的方法である. 対象物が2次元の<ins class="diffchange diffchange-inline"><math></ins>n<ins class="diffchange diffchange-inline">\,</math></ins>点からなる図形のときは, 対象物を座標軸に平行な辺からなる長方形で覆い, それを縦横<ins class="diffchange diffchange-inline"><math></ins>\lceil\sqrt{n}\ \rceil<ins class="diffchange diffchange-inline">\,</math></ins>等分し全部で<ins class="diffchange diffchange-inline"><math></ins>\Theta(n)=\lceil\sqrt{n}\ \rceil \times \lceil\sqrt{n}\ \rceil<ins class="diffchange diffchange-inline">\,</math></ins>個のバケットと呼ばれる小長方形領域に分割して図形を各バケットで切り出し管理する. すると問題を各バケット内での極めて単純な問題に帰着できることもしばしばあり, 高速に処理できることになる.</div></td></tr>
</table>
211.9.162.254
https://orsj-ml.org/orwiki/wiki/index.php?title=%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E6%B3%95&diff=3658&oldid=prev
122.17.2.240: 新しいページ: '【ばけっとほう (bucket method)】 幾何的な問題をより単純に高速に処理するための実際的方法である. 対象物が2次元の$n$点からなる...'
2007-07-12T15:29:29Z
<p>新しいページ: '【ばけっとほう (bucket method)】 幾何的な問題をより単純に高速に処理するための実際的方法である. 対象物が2次元の$n$点からなる...'</p>
<p><b>新規ページ</b></p><div>【ばけっとほう (bucket method)】<br />
<br />
幾何的な問題をより単純に高速に処理するための実際的方法である. 対象物が2次元の$n$点からなる図形のときは, 対象物を座標軸に平行な辺からなる長方形で覆い, それを縦横$\lceil\sqrt{n}\ \rceil$等分し全部で$\Theta(n)=\lceil\sqrt{n}\ \rceil \times \lceil\sqrt{n}\ \rceil$個のバケットと呼ばれる小長方形領域に分割して図形を各バケットで切り出し管理する. すると問題を各バケット内での極めて単純な問題に帰着できることもしばしばあり, 高速に処理できることになる.</div>
122.17.2.240