基単調図形に分割可能な最大重み領域を得る基線の配置問題
スポンサーリンク
概要
- 論文の詳細を見る
本論文では,ピクセルグリッドから最大重み領域を切り出す問題を扱う.ただし,切り出された領域は,基線に対して基単調図形に分割できなければならない.n×nピクセルグリッドと基線が与えられたとき,この問題はO(n^3)時間で解けることが知られている.これに対し本論文では,ピクセルグリッドのみが与えられたとき,k本の基線を最適に配置することはNP困難であることを示す.さらに,この配置問題に対し,O(n^3)時間の2倍近似アルゴリズムを与える。また,多項式時間で求解できるいくつかのケースや問題の変種も示す.
- 2012-04-20
著者
-
小野 廣隆
九州大学大学院システム情報科学研究院
-
小野 廣隆
九州大学
-
徳山 豪
東北大学大学院情報科学研究科
-
伊藤 健洋
東北大学大学院情報科学研究科
-
堀山 貴史
京都大学大学院情報学研究科
-
堀山 貴史
埼玉大学情報システム工学科
-
堀山 貴史
埼玉大学理工学研究科
-
上原 隆平
北陸先端科学技術大学院大学情報科学研究科
-
上原 隆平
駒澤大学自然科学教室
-
上原 隆平
北陸先端科学技術大学情報科学研究科
-
上原 降平
北陸先端科学技術大学院大学情報科学研究科
-
宇野 毅明
東京工業大学
-
宇野 毅明
東京工業大学経営工学専攻
-
宇野 毅明
東京工業大学システム科学
-
大舘 陽太
群馬大学工学部情報工学科
-
宇野 毅明
国立情報学研究所情報学プリンシプル研究系
-
小野 廣隆
九州大学システム情報科学府
-
伊藤 健洋
東北大学情報科学研究科
-
宇野 毅明
国立情報学研
-
ガオタントン ナスダ
東北大学大学院情報科学研究科
-
大舘 陽太
北陸先端科学技術大学院大学
-
ガオタントン ナスダ
東北大学 大学院情報科学研究科
-
堀山 貴史
埼玉大学情報メディア基盤センター
関連論文
- 画像切り出しに対するアルゴリズムの提案 (アルゴリズムと計算機科学の数理的基盤とその応用)
- センサーネットワークの位相情報の検知に関する研究 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 複数のデジタル図形の最適切り出しについて
- 基本図形分割可能領域の最適切り出しアルゴリズム
- 不完全情報渋滞ゲームの近似的ナッシュ遷移の収束性 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 任意のカバー時間を持つ木の構成法 (アルゴリズムと計算機科学の数理的基盤とその応用)
- Multiple Random WalkのCover Timeについて (アルゴリズムと計算機科学の数理的基盤とその応用)
- 高速復元可能な接尾辞配列圧縮法(FIT推薦論文)(情報・システム基礎)
- 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
- 非交差最小木の計算複雑度のパラメタ依存について
- Wireless Ad-Hocネットワークにおける干渉軽減法に関する研究
- 量子アルゴリズムによる近似文字列出現頻度問い合わせ
- メトロポリスウォークの到達時間及び全訪問時間に関するタイトな上界
- 証明書分散問題の近似可能性について
- グラフ上の線形Cover Timeランダムウォーク実現の必要条件
- 都市距離空間への新規高速道路の最適建設問題に対する擬凸最適化を用いた改良アルゴリズム
- ヨーロピアンアジアンオプションの効率的な価格付けの手法 : AMOアルゴリズムの実装と解析の改良
- 進化木のQuarted distanceの計算アルゴリズムの実装
- 多変数パラメトリック探索による最小値最大最適化問題の解法
- 負荷分散枝被覆問題に対する最適性とアルゴリズム
- 最適ハイウェイ配置問題
- 局所情報を用いたスケールフリーネットワークの探索
- 2-F-11 An O(n log^2 n)-Time Algorithm for L(2,1)-Labeling of Trees
- RA-002 木のL(2,1)-ラベリングのためのO(n log^2 n)時間アルゴリズム(モデル・アルゴリズム・プログラミング,査読付き論文)
- 木のL(2,1)-ラベリングに対するO(n^)時間アルゴリズム
- 2.高密度部分グラフの抽出 : その計算限界と打破(特定領域研究「新世代の計算限界-その解明と打破-」)
- 地形図からの最適ピラミッドの構成アルゴリズム
- 多値属性を用いた最適なデータセグメンテーションを生成するアルゴリズム
- ランダムアルゴリズムの話題から
- 最大出次数最小化問題の各種グラフクラスに対する計算複雑さ
- センサーネットワークの位相情報の検知に関する研究 (コンピュテーション)
- Geometric Problems on Ad-Hoc Network Design (Computational Geometry and Discrete Mathematics)
- D-022 動画に対するコメントを利用した自動Web検索システム(データベース,一般論文)
- A-003 アドホックネットワーク上でのランダム局所近傍を利用した幾何ルーティングアルゴリズムの設計と解析(モデル・アルゴリズム・プログラミング,一般論文)
- RA-006 リストページ自動分割問題の最適グラフ分割を用いた解法の提案と評価(モデル・アルゴリズム・プログラミング,査読付き論文)
- アドホックネットワーク上でのランダム局所近傍を利用した幾何ルーティングアルゴリズムの設計と解析
- メッシュネットワークにおけるジオメトリックルーティングに関する研究
- 数学的整合性を持つデジタル直線集合
- ディジタル星型領域とその応用
- D_036 Webデータの自動抽出とデータ変換(D分野:データベース)
- 関数近似における幾何学アルゴリズムの最近の進展 : データ解析への応用に向けて(新世代の計算限界-その解明と打破-招待解説論文)
- Web検索結果におけるクラスタリングアルゴリズムの研究
- アメリカン・アジアンオプションの価格の近似に対する計算幾何手法的アプローチ
- アメリカン・アジアンオプションの価格付けに対する計算幾何手法を用いた近似アルゴリズム(計算機科学の理論とその応用)
- ヨーロピアン・アジアンオプションの価格付けに関する近似的解法
- ディスクレパンシー基準によるディジタルハーフトーニング : 自動評価手法と最適化手法
- 実数列の大域的丸めの数え上げ
- 可変形状ラベリング問題に対するアルゴリズム
- 木の(p, q)-全ラベリング問題
- 自己安定リーダー選挙MPPにおける領域複雑度の上下界について
- グラフ及び領域空間に関する大域丸めの幾何学的性質について
- パラメトリックなポリマトロイドとその幾何学的応用
- 平面点集合のk巡回路被覆問題: kが定数の場合の多項式時間近似スキーム
- 外平面的グラフの(2,1)-全ラべリング数のタイトな上界
- 全二分木の簡潔な表現
- 高頻度なフレーズの検索が高速な索引
- グラフの最小出次数最大化問題
- 正規分布に従う枝重みをもつグラフにおける最小全域木コストの分布関数の近似手法
- A-028 ある種の不完全情報渋滞ゲームの近似的ナッシュ遷移の収束性(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- 混合ドミノタイリングの連結性
- 木のL(2, 1)-ラベリングに対する線形時間アルゴリズム
- A-023 接尾辞木に対する二分木化と簡潔データ構造による圧縮(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- A-022 圧縮された接尾辞配列を用いた近似文字列照合(A分野:モデル・アルゴリズム・プログラミング,一般論文)
- RA-007 高速復元可能な接尾辞配列圧縮法(モデル・アルゴリズム・プログラミング,査読付き論文)
- 近傍ハッシュ法によるエラー許容頻出パターン列挙(一般セッション3)
- 近傍探索の解合流性に基づく並列局所探索法の考察(計算理論とアルゴリズムの新展開)
- 移動物体回収問題 : ロボットに効率良く物体を回収させるアルゴリズムの設計のために(学生/教養のページ)
- k-集合合意問題を解く故障検知器
- 移動物体回収問題
- 隠れマルコフモデルを用いたDNA配列設計
- 負荷分散セミマッチングにおける最適性について
- DS-1-10 DNA構造変化の特徴解析(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- 故障数制限付きリーダー選挙問題に対する故障検知器
- ホーン理論の内包・外包に対する演繹推論
- センサーネットワークにおける省電力高信頼なデータ伝送(計算機科学の理論とその応用)
- DNA計算における局所探索法による反応障壁近似計算
- DNA計算における局所探索法による反応障壁近似計算
- 最大出次数を最小化するグラフ有向化について
- 量子回路における定数段加算器の設計(計算理論)
- Approximating the path-distance-width for $k$-cocomparability graphs (Mathematical Foundations and Applications of Computer Science and Algorithms)
- DS-1-6 MPPモデルにおけるリーダー選挙問題の容量複雑性(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- 非同期匿名ロボットによる最適マッチングを用いたパターン形成アルゴリズム (計算機科学とアルゴリズムの数理的基礎とその応用)
- マッチングを用いたパターン形成アルゴリズム
- センサーネットワークにおける省電力高信頼なデータ伝送(計算理論とアルゴリズムの新展開)
- 非同期分散システムにおける故障検知器と故障計数器について(計算理論とアルゴリズムの新展開)
- DNA 分子の濃度と反応速度の関係解析(計算理論とアルゴリズムの新展開)
- 最大支配問題
- タイル縁に上書きルールを用いた敷き詰め問題
- タイル縁に上書きルールを用いた敷き詰め問題
- 効率の良い罫線描画について
- 文書データベースへの効率的な索引付けとその更新に関する研究
- 最小重み負荷分散枝被覆について
- ランダムグラフ上の多種ランダムウォークの全訪問時間 (アルゴリズムと計算理論の新展開)
- On the base-line location problem for the maximum weight region decomposable into base-monotone shapes (New Trends in Algorithms and Theory of Computation)
- 次数上下界制約付きグラフ向き付けにおけるペナルティ最小化
- Reconfiguration of List L(2,1)-Labelings in a Graph (コンピュテーション)
- 基単調図形に分割可能な最大重み領域を得る基線の配置問題
- 次数上下界制約付きグラフ向き付けにおけるペナルティ最小化
- RA-002 文字列圧縮を用いたネットワークセキュリティにおけるインシデント検出(アルゴリズムと応用(2),A分野:モデル・アルゴリズム・プログラミング)
- グラフのリストL(2,1)ラベリングの遷移可能性(一般)