Parallel Congruent Regions on a Mesh-Connected Computer

摘要

In this paper, we present a parallel algorithm for solving the congruent region problem of locating all the regions congruent to a test region in a planar figure on a mesh-connected computer(MCC). Given a test region with κ edges and a planar figure with n edges, it can be executed in O(n~(1/2)) time if each edge in the test region has unique length; otherwise in O(κn~(1/2)) time on MCC with n processing elements(PE's), and in O(n~(1/2)) time for both cases using κn PE's, which is optimal on MCC within constant factor. We shall show that this can be achieved by deriving a new property for checking congruency between two regions which can be implemented efficiently using RAR and RAW operations. We also show that our parallel algorithm can be directly used to solve point set pattern matching by simple reduction to the congruent region problem, and it can be generally implemented on other distributed memory models.