ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract. 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 that 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 give a nontrivial 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 four-dimensional space.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009388
