離散グラフの選択的詳細化に基づく多面体上の近似最短経路算出とその応用

• Item type: SIG Technical Reports(1)
• 公開日: 1999-12-10
• タイトル: 離散グラフの選択的詳細化に基づく多面体上の近似最短経路算出とその応用
• タイトル / 言語: en
• タイトル: Approximate Shortest Path on a Polyhedral Surface Based on Selective Refinement of the Discrete Graph and Its Applications
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 理化学研究所素形材工学研究室
• 著者所属: 東京大学大学院工学系研究科精密機械工学専攻
• 著者所属(英): en
• 著者所属(英): RIKEN, Materials Fabrication Lab.
• 著者所属(英): en
• 著者所属(英): University of Tokyo, Dept. Precision Engineering
• 著者名: 金井, 崇; 鈴木, 宏正
• 著者名(英): Takashi, Kanai; Hiromasa, Suzuki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 多面体モデル上の近似最短経路を計算するための，新しいアルゴリズムについて提案する．本手法は主にダイクストラの手法を用い，多面体の離散グラフの選択的詳細化に基づく．このアルゴリズムは近似手法であるが，高速である，実装が簡単である，近似精度が高い，数値的に頑健である，などいくつかの重要な利点を持つ．また，本近似アルゴリズムと，非凸多面体の正確な最短経路を計算することのできる拡張Chen & Han (C)アルゴリズムに対し，計算精度と計算時間に関する比較を行った．その結果，我々の例題では，ECHアルゴリズムに比べて0.4％以内の近似精度に収まる経路が，おおよそ100-1000倍の速さで求めることができた．さらに，本近似アルゴリズムの形状モデリングに対する二つの応用についても議論する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A new algorithm is proposed for calculating the approximate shortest path on a polyhedral surface. The method mainly uses Dijkstra's algorithm and is based on selective refinement of the discrete graph of a polyhedron. Although the algorithm is an approximation, it has the significant advantages of being fast, easy to implement, high approximation accuracy, and numerically robust. The approximation accuracy and computation time are compared between this approximation algorithm and the extended Chen & Han (ECH) algorithm that can calculate the exact shortest path for non-convex polyhedra. The approximation algorithm can calculate shortest paths within 0.4% accuracy to roughly 100-1000 times faster than the ECH algorithm in our examples. Two applications are discussed of the approximation algorithm to geometric modeling.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10100541
• 書誌情報: 情報処理学会研究報告グラフィクスとCAD（CG）; 巻 1999, 号 105(1999-CG-097), p. 13-18, 発行日 1999-12-10
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会