AbstractLet M be a 2-dimensional colored map which has been digitized into a large 2-dimensional array (M). We define a class of languages (called rectilinear) to describe our digitized maps and classify them based on their level of succinct representation. We also study the map compression problem, i.e., the problem of finding for any given map a shortest description within a given language. For one dimensional maps we show that a shortest description can be generated quickly for some languages, but for other languages the problem is NP-hard. We also show that a large number of linear time algorithms for our languages generate map descriptions whose length is at most twice the length of the minimum length description. For all our languages we show that the two dimensional map compression problem is NP-hard. Furthermore, for one of the most succinct of our languages we present evidence suggesting that finding a near-optimal map compression is as difficult as finding an optimal compression.
Categories and Subject Descriptors: E.4 [Coding and Information Theory]; I.4.2 [Image Processing]: Compression (Coding); F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems
Additional Key Words and Phrases: data compression, maps, images, computational complexity