凸多角形に対する包含多角形列の計算
スポンサーリンク
概要
- 論文の詳細を見る
凸多角形Pに対し,Pを含むk角形の列{P_k}_<k≥3>を計算する問題を扱う.本稿では,この問題を解く2つの手法を提案する.最初の手法は,kごとに最小面積の包含k角形を計算する手法で,最適法と呼ぶ.もう一方の手法は,出力されたk角形にその時点での最小面積の三角形を加え,(k-1)角形を逐次的に構成する手法である.これを貪欲法と呼ぶ.これら2つの手法を実装し,凸多角形に対し計算機実験を行った.その結果k=3の場合を除き,面積という観点で,貪欲法が最適法と同程度の面積を持つ包含k角形列を出力することがわかった.
- 一般社団法人情報処理学会の論文
- 2008-10-31
著者
関連論文
- 連載開始にあたって(プログラミング,何をどう教えているか)
- 単純多角形に対する包含多角形列の構成法
- 絶対近傍の被覆率と点配置
- 構図に基づく類似画像検索のための類似度
- 画像の領域分割に基づく類似画像検索(画像検索,アーカイブ)
- K-023 領域分割に基づく類似画像検索のrunlength符号化による高速化(K分野:教育工学・福祉工学・マルチメディア応用)
- 多次元データマイニングによるWeb空間の構造分析の評価
- 多構造データベース演算を用いたログデータ分析の試み
- D_019 多次元データマイニングを用いたWeb空間の構造解析の評価(D分野:データベース)
- N-OPS : 系列データベースにおける連続系列パターンの探索算法(データベース)
- 任意のL_p距離関数による検索が可能な索引構造(セッション3)
- 任意のL_p距離による検索を可能とする距離変換規則
- ストレージシステムにおけるデーター貫性を保証したアーカイブ取得方式(ストレージ技術, データ工学論文)
- 楽曲圧縮過程において算出される自己相関係数列を用いた楽曲の節長抽出と構造分析(音楽制作・音楽分析)
- 楽曲圧縮過程において算出される自己相関係数列を用いた楽曲の節長抽出と構造分析
- 多次元的なログデータマイニングを実現するデータキューブ機構の提案
- D-021 高頻度アイテムセットによる多次元的なログデータ分析を支援するデータキューブ機構(D.データベース)
- D-4-9 高頻度アイテムセット分析を行うデータキューブ機構アイテムセットキューブによるWebログ分析(D-4. データ工学)
- 問合せ分布を考慮したR木における領域分割方式(データベース)
- LD-5 問い合わせ分布に適応した多次元ファイル編成法GR木のアーカイブ環境への適用(D. データベース)
- 自己相関特徴量を用いた圧縮楽曲データからの構造抽出
- ウェーブレット分解係数の階層的相関関係を用いたテクスチャ類似画像検索(:ビジュアルデータベース)
- TwinVQに基づいたビットレートに依存しない音楽検索のための特徴量
- TwinVQに基づいたビットレートに依存しない音楽検索のための特徴量
- 1Q-9 ウェーブレット変換を用いたテクスチャ検索のための質問画像の生成法
- 1P-7 ビットレートの異なるTwinVQオーディオデータの類似曲検索のための特徴量
- ウェーブレット変換を用いた対話的類似画像検索と民俗資料データベースへの適用 (人文科学とコンピュータ)
- 5T-5 ウェーブレット変換と高次局所自己相関特徴量を用いた対話的類似画像検索システム
- D-4-12 制約つき相関性ルール発見問題における次元削減の適用
- マスク集合を用いた制約つき相関性ルール発見問題の高速化
- 自動微分法と区間演算による陰曲面近似システムの試作と評価
- ウェーブレット変換を用いた画像データベースにおける対話的類似画像検索方式
- 曲の局所パターン特徴量を用いた類似曲検索・感性語による検索
- ウェーブレット変換を用いたテクスチャ特徴量
- 連想型ルール発見問題における追加データの処理方式
- 永続オブジェクト指向スクリプト言語を用いた移動計算機向け情報検索機構の実現
- 移動計算機における情報ベース検索スクリプトの合成方式
- データマイニングにおける追加データの処理方式
- BAT(バルクアクセス・トランザクションを用いたデータウェアハウスの構築
- 高速自動微分法と区間解析を用いたレイトレーシング法の評価
- ウェーブレット変換を用いた画像のテクスチャ解析
- 音楽データベースにおける感性検索の試み
- スクリプト言語による移動計算機向け永続オブジェクトシステム
- 高速自動微分を用いた区間解析によるレイトレーシング法
- リーマン多様体でのボロノイ図に必要な点数の評価
- 単連結完備多様体におけるボロノイ図のファセット数の評価
- 木情報源の符号化 (符号と暗号の代数的数理)
- ハイブリッド型XML - 関係データベースにおけるキーワード検索
- ハイブリッド型XML - 関係データベースにおけるキーワード検索
- 永続オブジェクト指向スクリプト言語を用いた移動計算機向け情報検索機構の実現
- データベースを用いた多エージェント系のシミュレーション方式
- 6S-9 グラフデータベースにおけるTop-kキーワード検索方式の改良と評価(XML・グラフデータベース,学生セッション,データベースとメディア,情報処理学会創立50周年記念)
- 3R-8 多次元的なWeb空間マイニングを行うデータベースシステムの実現 : 一般化された制約条件への対応(Web応用,学生セッション,データベースとメディア,情報処理学会創立50周年記念)
- A-020 グラフデータベースにおけるキーワード検索方式の改良(モデル・アルゴリズム・プログラミング,一般論文)
- スクリプト言語を用いた移動計算機向けの永続オブジェクトシステム
- 直交Wavelet変換を用いた類似画像検索方式
- 内容に基づいた画像と楽曲の検索(類似尺度と情報検索)
- ウェーブレット変換を用いた対話的類似画像検索システム
- 画像内容に基づいた画像検索システム
- ハフマン木の最適領域の隣接性について
- Computing a Sequence of Circumscribing Polygons for Convex Polygon (Computational Geometry and Discrete Mathematics)
- 凸多角形に対する包含多角形列の計算
- 最適二分探索木を与える領域と回転操作及び三角形分割
- 検索確率をもつ二分探索木の探索長の最適期待値を与える領域分割の生成
- 包含多角形列の計算手法とその実験的解析 (Theoretical Foundations of Computing)
- mm-GNAT における分割点集合の選択手法に関する研究 (アルゴリズムと計算理論の新展開)
- JAPAN-KOREA Joint Workshop'97 on Algorithms and computation参加報告
- D-4-2 パイプライン型リソースマネージャーにおけるトランザクション処理方式の検討
- データ圧縮における最新アルゴリズム[V・完] : 算術符号,乱数生成と区間アルゴリズム
- 乱数生成と情報源符号化(データ圧縮)
- 包含多角形列の計算手法とその実験的解析