超平面アレンジメントに基づく多次元空間幾何アルゴリズムの実装と評価

• Item type: SIG Technical Reports(1)
• 公開日: 2003-07-16
• タイトル: 超平面アレンジメントに基づく多次元空間幾何アルゴリズムの実装と評価
• タイトル / 言語: en
• タイトル: HA - face Complex Spatial Data Model for Uniform Representation of Data and Algorithms
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 九州大学 大学院 システム情報科学研究院
• 著者所属: 九州大学 大学院 システム情報科学研究院
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Electrical Engineering, Kyushu University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Electrical Engineering, Kyushu University
• 著者名: 金子, 邦彦; 牧之内, 顕文
• 著者名(英): Kunihiko, Kaneko; Akifumi, Makinouchi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本研究では，新しい空間データモデルとして，HA-face complexモデルを提案する．HA-face complex モデルでは，超平面アレンジメントのフェイスの複体として，空間物の位置と形を表現する．超平面アレンジメントのフェイスとは，ある次元の空間を複数の超平面で区切ったときにできる区画のことである．このモデルは，次元に特化しない空間データモデルであって，本質的に，任意の次元の空間データの表現に用いることができる．本研究では，HA-face complex モデル上で動く幾何計算（和や差や積などの集合論演算子や，交わる，離れている，含む，等しい，接するなどの位相関係述語）の効率よいアルゴリズムである localized divide-and-conquerと，2ステップリファインメントの提案も行う．実験によって，これらアルゴリズムの効果の確認も行っている．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper presents a kernel system for spatial database systems named Hawk's Eye. We implemented a new spatial data model named HA-face complex on Hawk's Eye. The model represents the spatial position and region of spatial objects of various dimensions in 2-, 3- or 4- dimensional space uniformly. A spatial object represented by the model is a finite set of hyperplane arrangement faces, each of which is a region in a hyperplane arrangement induced by hyperplanes in 2-, 3- or 4- dimensional space. We propose a new algorithm named localized divide-and-conquer to evaluate geometric operations and spatial relationships of two spatial objects represented by the model. The model is implemented on an object database system. Our experimental tests show that the localized divide-and-conquer is faster than other algorithms using an arrangement construction algorithm incremental or divide-and-conquer.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10112482
• 書誌情報: 情報処理学会研究報告データベースシステム（DBS）; 巻 2003, 号 71(2003-DBS-131), p. 219-226, 発行日 2003-07-16
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会