Voronoi線図を構成する逐次添加型算法の改良と諸算法の実験的比較
スポンサーリンク
概要
- 論文の詳細を見る
平面上にn個の母点P_i(i=1、……、 n)が与えられたとき、P_iに対するVoronoi多角形は、V_n(P_i)=∩__<j≠i> { P∈R^2 | b(P、P_i)<d(P、P_i) }(d(・、・)はEuclid距離)で定義される。V_n (P_i) (i = 1、……、n)による平面の分割はVoronoi線図と呼ばれ、地理情報処理、都市計画、生態学、補間法など幅広い分野に登場し、実用上も重要な概念である。Voronoi線図を効率的に構成する算法の研究は、計算幾何学の分野でも一つの中心的課題であり、最悪の場合の計算量がO(n log n)の再帰二分型やO(n^2)の逐次添加型の算法が提案され、オーダの意味で前者より速い算法はないことが理論的に知られている。本論文では、実際的見地から、大規模なVoronoi線図を平均的な意味で効率良く構成する算法を考察し、逐次添加型の算法における母点の添加順序をバケット法と四分木によって定める逐次四分添加法(quaternary incremental algorithm)を提案する。この算法の最悪の場合の計算量はO(n^2)であるが、母点が一様分布する場合には、再帰二分型の算法よりも格段に速くほぼO(n)で済むことが実験的に確かめられた。また、母点の分布が非一様の場合に対しても十分頑健であることも観察された。それらの実験結果を裏付けるためのいくらかの理論的考察も行なった。
- 社団法人日本オペレーションズ・リサーチ学会の論文
著者
-
大屋 隆生
(財)電力中央研究所
-
室田 一雄
筑波大学社会工学系
-
伊理 正夫
東京大学工学部計数工学科
-
大屋 隆生
電力中央研究所経済研究所情報システム部
-
伊理 正夫
東京大学
-
室田 一雄
Department Of Mathematical Informatics Graduate School Of Information Science And Technology Univers
関連論文
- A survey on convergence theorems of the dqds algorithm for computing singular values
- 定数関数に対し正確な値を与えるIMT型数値積分公式(並列数値計算アルゴリズムとその周辺)
- 特異値計算アルゴリズムdqds法の収束定理 (計算科学の基盤技術としての高速アルゴリズムとその周辺)
- 特異値計算アルゴリズムdqds法の理論保証付き超2次収束シフト戦略(理論)
- On Convergence of the dqds and mdLVs Algorithms for Computing Matrix Singular Values(Mathematical Sciences for Large Scale Numerical Simulations)
- Sinc-Gauss Sampling Formula(Mathematical Sciences for Large Scale Numerical Simulations)
- 特異値計算のためのdqds法とmdLVs法の収束性について(理論)
- Gauss核サンプリング公式の複素関数論による誤差評価(理論)
- 連続/離散ハイブリッドM凸関数に関する一考察
- 電気抵抗回路に基づくグラフ上の半教師付き学習機械(テーマセッション,文字認識・文書理解)
- Electric Network Kernel for Support Vector Machines(SVM)
- Electric Network Kernel for Support Vector Machines (Decision Theory and Optimization Algorithms)
- 2段階アルゴリズムによるSVMの解法
- 連続/離散ハイブリッド凸最適化とその最適性規準
- 2段階アルゴリズムによるSVMの解法 (数理最適化から見た「凸性の深み,非凸性の魅惑」)
- 半正定値計画法に対する主双対内点法の群対称性 (数理最適化の理論とアルゴリズム)
- 付値マトロイドの理論 : 多項式行列の組合せ構造
- Computing the Combinatorial Canonical Form of a Layered Mixed Matrix
- ロバスト混合整数計画に対するBenders分解法(応用)
- 近藤次郎先生,伊理正夫先生 対談(歴代会長からのメッセージ,学会創立50周年記念号)
- 離散凸最適化ソルバとデモンストレーションソフトウェアの公開
- Scaling Algorithms for M-convex Function Minimization (Mathematical Optimization Theory and its Algorithm)
- M凸関数の最小化に対するスケーリングアルゴリズムとその実験的評価(組合せ)
- スケーリング技法を用いたM凸関数の最小化アルゴリズム
- Quasi M-convex Functions and Minimization Algorithms (Algorithm Engineering as a New Paradigm)
- Extension of M-convexity and L-convexity to Polyhedral Convex Functions : Extended Abstract (Continuous and Discrete Mathematics for Optimization)
- L凸関数に対する離散ヘッセ行列(離散最適化)
- M凸劣モジュラ流問題に対する容量スケーリング法
- M凸劣モジュラ流問題に対する容量スケーリングアルゴリズム(最適化(1))
- 電気抵抗回路に基づくグラフ上の半教師付き学習機械(テーマセッション,文字認識・文書理解)
- 計算誤差による暴走の心配のないソリッドモデラの提案
- 7p-L-1 音声の先験的分類可能性について
- 高度経営情報システムのパイロットモデル : DEMANDSの開発(DSS : デシジョンサポートシステム)
- 負極性沿面放電の進展モデルの進展パラメータ解析
- 負極性沿面放電の進展モデルの解析解の導出
- 負極性直線状沿面放電の進展モデルとその解析解
- モデルを用いた放電のシミュレーション
- 沿面放電の進展条件の検討[2]-解析解の導出法
- 沿面放電進展の相転移的考察(4)
- 計算幾何学と折れ線近似問題
- 最短路算法の実際的評価と新バケット法
- システムの異常の原因探索問題への一つのグラフ理論的接近法
- 回転変位を持つ対称構造物のブロック対角化手法〔英文〕
- 回転変位を持つ対称構造物のブロック対角化手法--理論編
- 回転変位を持つ対称構造物のブロック対角化手法--数値解析編
- 非解析的な関数を用いた変数変換型数値積分公式
- 非解析的な関数を用いた変数変換型数値積分公式について(並列数値計算アルゴリズムとその周辺)
- 大域的収束性をもつ代数方程式の解法 (数値計算のアルゴリズムとコンピューター)
- 高速自動微分法と区間解析とを用いた丸め誤差推定
- 高速自動微分法(II)
- 高速自動微分法(I)
- 最適化算法と高速自動微分法について(数値解析と科学計算)
- 高速自動微分法と区間解析とを用いた丸め誤差推定
- 高速微分法における変数消去のグラフ論的考察
- 最短路問題の"最適"算法について (計算の手間と能率化)
- 1-F-12 AHPにおける不完全一対比較方法の比較検討(AHP)
- ISAHP 2005/IFORS 2005に参加して(情報の窓)
- 通信ネットワークにおける伝送網の選択問題へのAHPの適用(AHPの応用)
- オフィスでの電力使用情報提示による電力有効利用支援効果 (企業事例)
- オフィスビルでの電力使用情報掲示の電力有効利用支援効果の分析(第5回企業事例交流会)
- オフィスでの電力有効利用支援に対する使用情報提示効果
- 電力会社におけるグループウェア利用の調査分析(特別セッション エネルギー産業におけるネットワークと業務効率化)
- 環境対策技術を考慮した電源開発計画策定モデル(電力のOR(1))
- 85-32 線形計画法の多項式時間の新解法
- 村田健郎, 小国 力, 唐木幸比古 著, "スーパーコンピュータ : 科学技術計算への適用", 丸善, B5判, vi+304p., \3,800, 1985
- Voronoi線図を構成する逐次添加型算法の改良と諸算法の実験的比較
- あふれのない浮動小数点表示方式
- あふれのない浮動小数点表示について (数値計算のアルゴリズムの研究)
- 多変数多項式行列の構造的弱既約性と構造的可制御性判定への応用
- Primal-Dual Combinatorial Relaxation Algorithms for the Maximum Degree of Subdeterminants
- 多項式行列に対する組合せ論的緩和法の実現について(組合せ最適化)
- 分割行列の階層的分解(II) : 同値変換(離散数学)
- 分割行列の階層的分解(I) : 相似変換(離散数学)
- 5. 区間演算を用いた丸め誤差解析 (精度保証付き数値計算とその応用)
- Voronoi図とSteiner木
- 与えられた平面分割のVoronoi近似
- モデリングにおける内的整合性について(特別講演)
- [招待論文]地理情報システムの現状と課題(グラフ,ペトリ,ニューラルネット,及び一般)
- [招待論文]地理情報システムの現状と課題(グラフ,ペトリ,ニューラルネット,及び一般)
- Runge-Kutta-Gill法について
- 日本応用数理学会の初心(フェロー)
- モデリング考(モデリング-最適化モデリング-)
- 国際化とGIS-ボーダーレスの時代, 異分野協同の必然性
- 地理情報システムの現状と課題
- 高橋秀俊,石橋善弘 : 電子計算機によるexactな計算の新方法(mod p演算の応用)(20世紀の名著名論)
- 地理情報システムにおけるデータ構造とアルゴリズム
- 日本応用数理学会創立十周年を迎えて(第10回年会総合講演より)
- 沿面放電進展の相転移的考察(3)
- 応用数理に関連する言語的諸問題(応用数理の遊歩道(15))
- 次元と行列に関する随想II(応用数理の遊歩道(14))
- 新世紀における空間データ基盤の役割(空間データ基盤の基礎と応用)
- 次元と行列に関する随想I(応用数理の遊歩道(13))
- 負極性直線状沿面放電モデルの検討
- 沿面放電進展の相転移的考察 (特集:平成10年度若手セミナ-「放電プラズマを科学する」)
- "一般性"を仮定した分割行列に関する最大最小定理とDulmage-Mendelsohn型分解(組合せ最適化)
- 独立マッチングの基本構造に関する一定理(組合せ最適化)
- Rigorous Proof of Cubic Convergence for the dqds Algorithm for Singular Values
- 離散凸解析(Discrete Convex Analysis)((離散可積分系と離散解析)
- 離散凸解析 : 組合せ最適化における凸性
- 地理情報システムの拡大・普及と標準化