動的凸包算法の高速化

• Item type: SIG Technical Reports(1)
• 公開日: 1994-09-21
• タイトル: 動的凸包算法の高速化
• タイトル / 言語: en
• タイトル: A Fast Algorithm for Dynamic Convex Hull Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 神戸大学工学部電子工学科
• 著者所属: 神戸大学工学部電子工学科
• 著者所属: 神戸大学工学部電子工学科
• 著者所属(英): en
• 著者所属(英): Department of Electronics Engineering Faculty of Engineering, Kobe University
• 著者所属(英): en
• 著者所属(英): Department of Electronics Engineering Faculty of Engineering, Kobe University
• 著者所属(英): en
• 著者所属(英): Department of Electronics Engineering Faculty of Engineering, Kobe University
• 著者名: 永井, 靖; 太田有三; 羽根田, 博正
• 著者名(英): Yasushi, Nagai; Yuzo, Ohta; Hiromasa, Haneda
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 高次元の凸包問題の動的凸包算法としては、Beneath?Beyonod定理に基づくBeneath?Beyond法が提案されている。この方法はすべてのフェイスの情報を利用するため構成するポリトープの次元が高い場合多くの記憶容量を必要とし、その更新のための時間が長くなるという欠点があった。本報告では、高次元の動的凸包算法においてポリトープを表現するのにファセットとサブファセットとその包含関係だけで十分であることを示し、それに基づいた動的凸包算法を提案する。そして、インプリメントにおいて有用ないくつかの結果を導出し、それらに基づいた動的凸包算法を提案している。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The Beneath-Beyond method is well known as one of the dynamic convex hull maintenance methods, which based on Beneath-Beyond Theorem. In case the dimension of the polytop is high, Beneath-Beyond method requires very long computing time and huge storage, because the method needs all faces. The purpose of this paper is to propose a dynamic convex hull maintenance method for high dimensions. This method uses the information of facets and subfacets of the polytope and subsfacets contained by each facet. Moreover, several useful results relating the implementation of the method are derived. An algorithm based on these obatined results is presented.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1994, 号 82(1994-AL-041), p. 97-104, 発行日 1994-09-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会