平面上の点集合の平衡分割問題
スポンサーリンク
概要
- 論文の詳細を見る
平面上にmq個の白点集合Sとnq個の赤点集合Tがあり、S∪Tのどの3点も同一直線上にはないものとする。すると、S∪Tを下記の2つの条件を満たすようなq個の集合P_1, P_2, ..., P_qに分割できるという予想を与え、これがn=1のとき成り立つことを示したが、今回はn=2のときにもこの予想が成り立つことを証明する。またその証明から、所望の分割を得るO(N^2logN)のアルゴリズムもえられる、ただしN=mq+nqである。(1)すべてのの1≤i<j≤qに対して、conv(P_i)∩conv(P_j)=φである。(2)すべての1≤i≤qに対して、|P_i∩S|=n and |P_i∩T|=mがなりたつ。
- 一般社団法人情報処理学会の論文
- 1998-07-22
著者
関連論文
- 平面格子上の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年のあゆみ (前原濶教授退職記念号)