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

D. Eppstein, M.J. van Kreveld, B. Speckmann, F. Staals

Research output: Contribution to conferenceAbstractAcademic

65 Downloads (Pure)


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 languageEnglish
Publication statusPublished - 2012


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

Cite this