Improved grid map layout by point set matching

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

Research output: Contribution to journalArticleAcademicpeer-review

17 Citations (Scopus)
346 Downloads (Pure)


Associating the regions of a geographic subdivision with the cells of a grid is a basic operation that is used in various types of maps, like spatially ordered treemaps and Origin-Destination maps (OD maps). In these cases the regular shapes of the grid cells allow easy representation of extra information about the regions. The main challenge is to find an association that allows a user to find a region in the grid quickly. We call the representation of a set of regions as a grid a grid map. We introduce a new approach to solve the association problem for grid maps by formulating it as a point set matching problem: Given two sets A (the centroids of the regions) and B (the grid centres) of n points in the plane, compute an optimal one-to-one matching between A and B. We identify three optimisation criteria that are important for grid map layout: maximise the number of adjacencies in the grid that are also adjacencies of the regions, minimise the sum of the distances between matched points, and maximise the number of pairs of points in A for which the matching preserves the directional relation (SW, NW, etc.). We consider matchings that minimise the L1-distance (Manhattan-distance), the ranked L1-distance, and the L22-distance, since one can expect that minimising distances implicitly helps to fulfill the other criteria. We present algorithms to compute such matchings and perform an experimental comparison that also includes a previous method to compute a grid map. The experiments show that our more global, matching-based algorithm outperforms previous, more local approaches with respect to all three optimisation criteria. Keywords: Grid map; point-set matching; visualization
Original languageEnglish
Pages (from-to)101-122
Number of pages22
JournalInternational Journal of Computational Geometry and Applications
Issue number2
Publication statusPublished - 2015


Dive into the research topics of 'Improved grid map layout by point set matching'. Together they form a unique fingerprint.

Cite this