点集合の距離重複度列のノルムと最大部分集合問題
書誌事項
- タイトル別名
-
- Distribution of Distances and Triangles in a Point Set and Algorithms for Computing the Largest Common Point Set
この論文をさがす
説明
ユークリッド平面内の二つの点集合P,Qに対して、各々の部分集合で、互いに合同なものを共通部分集合という。この論文では点数最大の共通部分集合を計算する問題(LCP)を考察する。そのために、距離重複度ベクトルの内積の概念を導入し、その解析を行なう。さらに、高次元の場合に、この内積の概念を拡張する。内積の値に対する上界を用いて、LCPの高速解法を設計する事が出来る。この講演原稿では、ページ制限の都合で4次元以上の場合の結果の解説は省く。
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 various algorithms for LCP, and a non-trivial upper bound on λ(P,Q). We generalize this notion to higher dimensions, give some upper bounds 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|.
収録刊行物
-
- 情報処理学会研究報告. AL, アルゴリズム研究会報告
-
情報処理学会研究報告. AL, アルゴリズム研究会報告 55 61-68, 1997-01-23
一般社団法人情報処理学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1570572702210942464
-
- NII論文ID
- 110002812065
-
- NII書誌ID
- AN1009593X
-
- ISSN
- 09196072
-
- 本文言語コード
- en
-
- データソース種別
-
- CiNii Articles
