Computing a Good Shape

One of the criteria of a good grid map or small multiple with gaps is that the overall appearance of the grid map resembles that of the actual geographic shape of the region being shown.

There are various ways to quantify such resemblance, such as the Hausdorff distance, Fréchet distance and symmetric difference. Each has its own benefits and drawbacks, but we have proven that for either of these metrics, it is NP-hard to compute the grid shape that best matches the geographic shape, if we enforce that this grid shape is one single shape. “NP-hard” means that it is generally believed (though not proven currently) that there is no efficient exact algorithm to compute the solution.

These results can be found in our algorithmic paper “Mapping polygons to a grid”, as well as an online preprint “Discretized Approaches to Schematization”.

The first of these papers also presents some positive results: if we do not insist on the best possible shape, but rather on a “good-enough” shape, we can develop fast algorithms to compute solutions.