On similarity between finite sets in plane

摘要

We present a Θ(n log n) time algorithm to check similarity, under isogonal affine transformation (i.e. translation, rotation and scaling), of two given sets of n points in plane. We obtain an O(n log n) time algorithm and establish Ω(n log n) lower bound for this problem under the linear search tree model. Our analysis implies that the main source of complexity for this problem arises from the “combinatorial” nature rather than the “affiness” of the problem.