点集合の距離重複度列のノルムと最大部分集合問題

• Item type: SIG Technical Reports(1)
• 公開日: 1997-01-23
• タイトル: 点集合の距離重複度列のノルムと最大部分集合問題
• タイトル / 言語: en
• タイトル: Distribution of Distances and Triangles in a Point Set and Algorithms for Computing the Largest Common Point Set
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学医科学研究所ヒトゲノム解析センター
• 著者所属: 日本アイ・ビー・エム東京基礎研究所
• 著者所属: 日本アイ・ビー・エム東京基礎研究所
• 著者所属(英): en
• 著者所属(英): Human Genome Center, Institute of Medical Science, University of Tokyo
• 著者所属(英): en
• 著者所属(英): IBM Tokyo Research Laboratory
• 著者所属(英): en
• 著者所属(英): IBM Tokyo Research Laboratory
• 著者名: 阿久津, 達也; 玉木, 久夫; 徳山, 豪
• 著者名(英): Tatsuya, Akutsu; Hisao, Tamaki; Takeshi, Tokuyama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: ユークリッド平面内の二つの点集合P，Qに対して、各々の部分集合で、互いに合同なものを共通部分集合という。この論文では点数最大の共通部分集合を計算する問題(C)を考察する。そのために、距離重複度ベクトルの内積の概念を導入し、その解析を行なう。さらに、高次元の場合に、この内積の概念を拡張する。内積の値に対する上界を用いて、LCPの高速解決を設計する事が出来る。この講演原稿では、ページ制限の都合で4次元以上の場合の結果の解説は省く。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper considers the following problem which we call the largest common point set problem (LCP): given two point sets P and Q in the Euclidean plane, find a subset of P with the maximum cardinality which is congruent to some subset of Q. We introduce a combinatorial-geometric quantity λ(P,Q), which we call the inner product of the distance-multiplicity vectors of P and Q, show its relevance to the complexity of of various algorithms for LCP, and give a non-trivial upper bound on λ(P,Q). We generalize this notion to higher dimensions, give some upper bunds on the quantity, and apply them to algorithms for LCP in higher dimensions. Along the way, we prove a new upper bound on the number of congruent triangles in a point set in the four-dimensional space (which we omit in this abstract). Table 1 summarizes the algorithmic results of this paper, where we omit logarithmic factors and K denotes the size of the largest common point set. We have included some results on the largest similar point set problem (LSP), congruent copy detection (CCD) and the similar copy detection problem (SCD), where n = |P|, m = |Q|.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1997, 号 8(1996-AL-055), p. 61-68, 発行日 1997-01-23
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会