Fractals can be an effective approach for several applications other than image coding and transmission: database indexing, texture mapping, and even pattern recognition problems such as writer authentication. However, fractal-based algorithms are strongly asymmetric because, in spite of the linearity of the decoding phase, the coding process is much more time consuming. Many different solutions have been proposed for this problem, but there is not yet a standard for fractal coding. This paper proposes a method to reduce the complexity of the image coding phase by classifying the blocks according to an approximation error measure. It is formally shown that postponing range\slash domain comparisons with respect to a preset block, it is possible to reduce drastically the amount of operations needed to encode each range. The proposed method has been compared with three other fractal coding methods, showing under which circumstances it performs better in terms of both bit rate and/or computing time.