##
Optimal Fractal Coding is NP-Hard

**
Matthias Ruhl and Hannes Hartenstein
**
*Data Compression Conference (DCC '97)*

Snowbird, March 1997

[Postscript, 226KB]

[PDF, 154KB]

### Abstract

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