### Abstract

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.

Original language | English |
---|---|

Pages | 205-208 |

Publication status | Published - 2012 |

## Fingerprint Dive into the research topics of 'One-to-one point set matchings for grid map layout'. Together they form a unique fingerprint.

## Cite this

Eppstein, D., van Kreveld, M. J., Speckmann, B., & Staals, F. (2012).

*One-to-one point set matchings for grid map layout*. 205-208.