nicht angemeldet
Momentan mache ich das Zusammenfassen mit einem Greedy-Algorithmus. Der ist auf keinen Fall optimal, aber dafür von der Laufzeit her polynomiell.
Eine integrale Optimierung wäre in der Tat np-vollständig, aber man kann ja ruhig mal 30 Sekunden oder so für die Komprimierung warten.
Die Optimierung muß dann so ablaufen, daß die größte Fläche gesucht wird, gemerkt und markiert. Das dann iterieren bis kein Pixel mehr übrig ist.
Dann ist es aber wirklich optimal :) Müßte man auch beweisen können.
Ganz im Gegenteil bin ich sicher, daß *das* nicht optimal ist (aber durchaus "gut", vor allem bei typischen Graphiken, für die GIF die optimale Darstellung wäre) und hatte deshalb den Knapsack-Algorithmus als Referenz angegeben.
Es geht ja nicht darum, eine große und unzählig viele kleine Flächen zu finden, sondern *möglichst wenige*. Das ist viel schwieriger - für den allgemeinen Fall gibt es nichts Besseres, als jede mögliche Kombination von Flächen durchzuprobieren. Und das sind *entsetzlich* viele ...
Mein Beispiel mit der diagonalen Linie und den Quadraten sollte zudem zeigen, daß die Lösung nicht einmal eindeutig sein muß und daß bestimmte Fälle durch "Hinsehen" leicht zu erkennen, aber schwer zu formalisieren sein werden.
Diese Mehrdeutigkeit wiederum könnte man dahingehend nutzen, diejenige Lösung auszuwählen, die vom Browser am schnellsten layoutet werden kann ...