Each image has layers to draw on.

There is an important case we need to decide on.
The layer can be stored in more than one format, corresponding to its size.
1. The layer can be as big as the image itself - this is the easiest option, all the layers have fixed, constant (between canvas size changes) size (possibly GIMP).
2. The layer is as big as its contents - there are few subcases to this approach:
    a) rectangular layer - quite easy to achieve, saves lot of memory, still it is far from ideal
    b) multiple-rectangular layer - a layer that consist of rectangular slices - encapsulates its contents quite closely but at the cost of additional processing time needed. Could be QRegion based, as it seems to implement some effective slicing algorithms.
    c) freeform layer - most complex approach possibly processing costs outweigh memory savings.

Approach 2 (though I don't know which subcase) seems to be implemented both in Krita and Photoshop.
In my (janisozaur) opinion approach 2b is the most feasible. Approach 2a could be developed first, and later on upgraded to 2b. There should be massive memory savings burdened with just a few computations more.
Post your ideas and opinions.

References:
http://krita.org/component/content/article/10-news/57-last-week-in-krita-week-32-and-a-bit-of-33

rawo [2010-08-23]
I'm fine with 2.b. But I'm not quite sure if the slicing is a good approach.
When drawing on a layer (which is an transparency one) in fact we put a lot of independent drawings on it. Then we have two issues:
1. all of the drawings are 'floating' on the layer.
2. some of the drawings are overlapping.
In the second case it would be nice to merge overlapping drawings into one.
Other solution is to,while drawing, merge all of the drawings in to one big enough to cover them.
Is this a correct approach or am I missing something? :)