平面上の2種点集合の平衡分割(セッション1)
スポンサーリンク
概要
- 論文の詳細を見る
平面上の一般の位置に置かれた赤点の集合Rと青点の集合Bに対して, もしag≦|R|<(a+1)gかつbg≦|B|<(b+1)gなら, 平面をg個の凸集合X_1∪…∪X_gに分割し, 各X_iにはaまたはa+1個の赤点と, bまたはb+1個の青点があるようにできる.また, この分割の存在証明からO(n^4)時間でこのような分割を求めるアルゴリズムが得られる.ただしnは点の総数である.
- 一般社団法人情報処理学会の論文
- 2006-01-20
著者
関連論文
- 平面格子上の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年のあゆみ (前原濶教授退職記念号)