幾何的交互道被覆と多項式時間アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
平面上の一般の位置に置かれたag+(a+1)h個の赤点と(a+1)g+ah個の青点に対して, 平面をg+h個の凸集合X_1U…UX_gUY_1U…UY_hに分割し, 各X_iにはa個の赤点とa+1個の青点があり、各Y_jにはa+1個の赤点とaの青点があるようにできる.ここで例えばa=2とおくと, 平面上に与えられた2g+3h個の赤点と3g+2h個の青点を、赤点と青点で交互に通り辺が直線分からなる位数5の交互道P_5で被覆できことがわかる.また, この分割の存在証明から一般のaにおける分割を求める多項式時間O(n^4)のアルゴリズムが得られる, ただしnは点の総個数である.さらに, 平面上の一般の位置に置かれた2g+1(≩5)個の赤点と(2g+1)b個の青点に対しても, 平面をg+1個の凸集合X_1UX_2U…UX_gに分割し, 各X_1には1個の赤点とb個の青点があり, 各X_i(2&InE;i&InE;g+1)には2個の赤点と2bの青点があるようにできる.そして, この分割を求める多項式時間アルゴリズムがある.
- 社団法人電子情報通信学会の論文
- 2001-09-07
著者
関連論文
- 平面格子上の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年のあゆみ (前原濶教授退職記念号)