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.
Article PDF
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received July 17, 1997, and in revised form March 6, 1998.
Rights and permissions
About this article
Cite this article
Akutsu, T., Tamaki, H. & Tokuyama, T. Distribution of Distances and Triangles in a Point Set and Algorithms for Computing the Largest Common Point Sets . Discrete Comput Geom 20, 307–331 (1998). https://doi.org/10.1007/PL00009388
Issue Date:
DOI: https://doi.org/10.1007/PL00009388