One-to-one point set matchings for grid map layout

We study several one-to-one point set matching problems which are motivated by layout problems for grid maps. We are given two sets A and B of n points in the plane, and we wish to compute an optimal one-to-one matching between A and B. We consider two optimisation criteria: minimising the sum of the L1-distances between matched points, and maximising the number of pairs of points in A for which the matching preserves the directional relation. We show how to minimise the total L1-distance under translation or scaling in O(n6 log3 n) time, and under both translation and scaling in O(n10 log3 n) time. We further give a 4-approximation for preserving directional relations by computing a minimum L1-distance matching in O(n2 log3 n) time