基単調図形に分割可能な最大重み領域を得る基線の配置問題
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,ピクセルグリッドから最大重み領域を切り出す問題を扱う.ただし,切り出された領域は,基線に対して基単調図形に分割できなければならない.n×nピクセルグリッドと基線が与えられたとき,この問題はO(n^3)時間で解けることが知られている.これに対し本論文では,ピクセルグリッドのみが与えられたとき,k本の基線を最適に配置することはNP困難であることを示す.さらに,この配置問題に対し,O(n^3)時間の2倍近似アルゴリズムを与える。また,多項式時間で求解できるいくつかのケースや問題の変種も示す.
- 2012-04-20
著者
-
小野 廣隆
九州大学大学院システム情報科学研究院
-
小野 廣隆
九州大学
-
徳山 豪
東北大学大学院情報科学研究科
-
伊藤 健洋
東北大学大学院情報科学研究科
-
堀山 貴史
京都大学大学院情報学研究科
-
堀山 貴史
埼玉大学情報システム工学科
-
堀山 貴史
埼玉大学理工学研究科
-
上原 隆平
北陸先端科学技術大学院大学情報科学研究科
-
上原 隆平
駒澤大学自然科学教室
-
上原 隆平
北陸先端科学技術大学情報科学研究科
-
上原 降平
北陸先端科学技術大学院大学情報科学研究科
-
宇野 毅明
東京工業大学
-
宇野 毅明
東京工業大学経営工学専攻
-
宇野 毅明
東京工業大学システム科学
-
大舘 陽太
群馬大学工学部情報工学科
-
宇野 毅明
国立情報学研究所情報学プリンシプル研究系
-
小野 廣隆
九州大学システム情報科学府
-
伊藤 健洋
東北大学情報科学研究科
-
宇野 毅明
国立情報学研
-
ガオタントン ナスダ
東北大学大学院情報科学研究科
-
大舘 陽太
北陸先端科学技術大学院大学
-
ガオタントン ナスダ
東北大学 大学院情報科学研究科
-
堀山 貴史
埼玉大学情報メディア基盤センター
関連論文
- 画像切り出しに対するアルゴリズムの提案 (アルゴリズムと計算機科学の数理的基盤とその応用)
- センサーネットワークの位相情報の検知に関する研究 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 複数のデジタル図形の最適切り出しについて
- 基本図形分割可能領域の最適切り出しアルゴリズム
- 不完全情報渋滞ゲームの近似的ナッシュ遷移の収束性 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 任意のカバー時間を持つ木の構成法 (アルゴリズムと計算機科学の数理的基盤とその応用)
- Multiple Random WalkのCover Timeについて (アルゴリズムと計算機科学の数理的基盤とその応用)
- 高速復元可能な接尾辞配列圧縮法(FIT推薦論文)(情報・システム基礎)
- 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
- 非交差最小木の計算複雑度のパラメタ依存について