Beneath - Beyond定理の改良と動的凸包算法

• Item type: SIG Technical Reports(1)
• 公開日: 1990-09-28
• タイトル: Beneath - Beyond定理の改良と動的凸包算法
• タイトル / 言語: en
• タイトル: Complement of Beneath - Beyond Theorem and Dynamic Convex Hull Maintenance
• 言語: 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
• 著者名: ?磊; 太田有三; 羽根田, 博正
• 著者名(英): Lei, Gong; Yuzo, Ohta; Hiromasa, Haneda
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本報告では，Beneath?Beyond定理の改良とそれに基づいた動的凸包算法について述べている．多次元の凸包問題の動的凸包算法としては，Beneath?Beyond法が提案されている．この方法はその理論的根拠を，Beneath?Beyond定理においているが，定理そのものが縮退を生ずる場合（新しく追加される点が現在の凸多面体の支持超平面の1つまたは幾つかに含まれる場合）には，完全でない．そのため，縮退を生ずる場合には，Beneath?Beyond法も正しく働かない．本報告では，まず，Beneath?Beyond定理において，完全でなかった場合を補完し，定理の改良を行っている．そして，インプリメントにおいて有用ないくつかの結果を導出し，それらに基づいた動的凸包算法を提案している．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The purpose of this paper is to show the complement of so called Beneath-Beyond Theorem and to propose a dynamic convex hull maintenance method. The beneath-beyond method is well known as one of the dynamic convex hull maintenance methods, which based on Beneath-Beyond Theorem. In case that the degeneracy (we means that the point to be added to the current polytope belongs to supporting hyperplanes) occurs, Beneath-Beyond Theorem is incorrect. A missed case is complemented to Beneath-Beyond Theorem. Moreover, several useful results relating the implementation of beneath-beyond method are derived. An algorithm based on these obatined results is presented.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1990, 号 79(1990-AL-017), p. 25-34, 発行日 1990-09-28
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会