Complexity aspects of map compression

The authors define a class of languages (called rectilinear) to describe coloured digitized maps and classify them on the basis of their level of succinct representation. The map compression problem is defined as the problem of finding for any given map a shortest description within a given language. For one dimensional maps, that a shortest description can be generated quickly for some languages, but for other languages the problem is NP-hard. A large number of linear time algorithms generate map descriptions whose length is at most twice the minimum.