平面格子上の2種点集合の平衡分割問題
スポンサーリンク
概要
- 論文の詳細を見る
平面格子上にある赤点の集合と青点の集合の分割について述べる.最初の定理は,ハム・サンドイッチの定理と類似する次の結果である.平面格子上にある2n個の赤点と2m個の青点に対して,これらを同時に2等分割する準直交分割が存在する.格子上の点集合において,各格子線上に高々1点しかその点がないとき,この点集合は一般の位置にあるという.また,各格子線との共通部分がひとつの直線分かまたは空集合となる連結領域を格子凸領域という.次に,一般の位置にある赤点集合と青点集合は凸領域によって3等分割できることも示す.つまり,平面格子上の一般の位置にある3n個の赤点と3m個の青点は,平面を3個の格子凸領域に分割して,各領域には赤点n個と青点m個が存在するようにできる.
- 一般社団法人情報処理学会の論文
- 2008-01-18
著者
関連論文
- 平面格子上の2種点集合の平衡分割問題
- 木をアクセス構造とする多画像視覚型秘密分散法
- サイクルをアクセス構造にもつ多画像視覚型秘密分散法
- 二面体群をアクセス構造に持つ多画像視覚型秘密分散法
- 平面上の2種点集合の平衡分割(セッション1)
- 平面上の3角格子と離散構造問題 (情報学シンポジウム特集号)
- Visual card games for boys and girls (ワイドバンドシステム・情報通信基礎サブソサイエティ合同研究会)
- Visual card games for boys and girls (情報セキュリティ・情報通信基礎サブソサイエティ合同研究会)
- Visual card games for boys and girls (情報理論・情報通信基礎サブソサイエティ合同研究会)
- 茨大型ライフゲーム
- 茨大型ライフゲーム(数理モデルの組合せ論的構造)
- 階層構造をもった暗号化ファイルシステムについて
- 階層構造をもった暗号化ファイルシステムについて
- 階層構造をもった暗号化ファイルシステムについて
- 階層構造をもった暗号化ファイルシステムについて
- 平面三角格子上におけるベンド数の少ないグラフ描画
- 幾何的交互道被覆と多項式時間アルゴリズム
- Complete Bipartite Geometric Graphs and Alternating Paths (情報学シンポジウム特集号)
- 平面上の点集合の平衡分割問題
- グラフの平面への直線埋込み問題
- 管理機能付き公開鍵暗号システム
- 管理機能付き公開鍵暗号システム
- 管理機能付き公開鍵暗号システム
- 管理機能付き公開鍵暗号システム
- 2つのグループのための視覚型カードゲーム(情報通信基礎サブソサイエティ合同研究会)
- 2つのグループのための視覚型カードゲーム(情報通信基礎サブソサイエティ合同研究会)
- 2つのグループのための視覚型カードゲーム(情報通信基礎サブソサイエティ合同研究会)
- 離散・計算幾何学国際会議(JCDCG) : 15年のあゆみ (前原濶教授退職記念号)