三角形族の中での直交探索

• Item type: SIG Technical Reports(1)
• 公開日: 1993-11-25
• タイトル: 三角形族の中での直交探索
• タイトル / 言語: en
• タイトル: Orthogonal queries in triangles
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 日本IBM東京基礎研究所
• 著者所属(英): en
• 著者所属(英): IBM Research, Tokyo Research Laboratory
• 著者名: 徳山, 豪
• 著者名(英): Takeshi, Tokuyama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 空間内の三角形または線分の集合に対して、軸方向の直交領域と交わる図形を全て列挙する問題（直交探索）に対して、効率の良いアルゴリズムを考える。もっとも興味深いのは、探索の効隼が、データの個数以外の様々な幾何学的パラメターに依存している事である。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We present an efficient orthogonal query data structure in a set of segments or triangles in space. The most important feature of our results is that the efficiency of the data structure is highly dependent on the geometric properties of the input set, as well as its cardinality. (1) Given a set of n segments in d-dimensional space, we give a data structure of O(m) space (m 〓 n log^<d-1>) that allows us to count the segments intersecting an orthogonal query window W in O^^~(√<K/m>) time. Here, K is the complexity of the arrangement of the images of segments projected onto axial subspaces. (2) Given a set of n triangles in d-dimensional space, we give a data structure of O(m) space that allows us to report the triangles intersecting an orthogonal query window in O^^~(√<K/m&t;+√<M>/m^<1/3>) time, not including the time for the output. Here, m is a parameter that coincides with the number of intersecting pairs of triangles if d=3, and K is as the same as in (1) for the set of edges of triangles.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1993, 号 104(1993-AL-036), p. 73-80, 発行日 1993-11-25
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会