M. Ruhl, H. Hartenstein. Optimal fractal coding is NP-hard. In Proceedings DCC'97 Data Compression Conference, J. A. Storer, M. Cohn (eds.), March 1997.
In fractal compression a signal is encoded by the parameters of a contractive trans-formation 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 admissi-ble 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.
Download paper:
Adobe PDF
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
@InProceedings{RuHa97a,
Author = {Ruhl, M. and Hartenstein, H.},
Title = {Optimal fractal coding is NP-hard},
BookTitle = {Proceedings DCC'97 Data Compression Conference},
editor = {Storer, J. A. and Cohn, M.},
Publisher = {IEEE Comp. Soc. Press},
Month = {March},
Year = {1997}
}