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

22 References

Bibliographic Information

Other Title
  • Distribution of Distances and Triangles in a Point Set and Algorithms for Computing the Largest Common Point Set

Search this article

Description

ユークリッド平面内の二つの点集合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|.

Journal

  • IPSJ SIG Notes

    IPSJ SIG Notes 55 61-68, 1997-01-23

    Information Processing Society of Japan (IPSJ)

References(22)*help

See more

Details 詳細情報について

  • CRID
    1570572702210942464
  • NII Article ID
    110002812065
  • NII Book ID
    AN1009593X
  • ISSN
    09196072
  • Text Lang
    en
  • Data Source
    • CiNii Articles

Report a problem

Back to top