Optimal Fractal Coding is NP-Hard

Matthias Ruhl and Hannes Hartenstein

Data Compression Conference (DCC '97)
Snowbird, March 1997

[Postscript, 226KB]

[PDF, 154KB]


In fractal compression a signal is encoded by the parameters of a contractive transformation whose fixed point (attractor) is an approximation of the original data. Thus fractal coding can be viewed as the optimization problem of finding in a set of admissible contractive transformations the transformation whose attractor is closest to a given signal. The standard fractal coding scheme based on the Collage Theorem produces only a suboptimal solution. We demonstrate by a reduction from MAXCUT that the problem of determining the optimal fractal code is NP-hard. To our knowledge, this is the first analysis of the intrinsic complexity of fractal coding. Additionally, we show that standard fractal coding is not an approximating algorithm for this problem.

Back to publications