Hi Gerd I tried out the v3 of the patch. It looks good, just looking at the pattern in inkscape. There is a shift towards smaller divs, though the average is still quite large (in area).
I don't think that the current algo is completely wrong. I think it is better to start with the complete data and divide it into smaller parts as that algo keeps the information of the location of elements, while your approach is likely to compare many bboxes which are (too) far away from each other.
Yes, implementation speed might require some more complexity - but it seems that it should produce a division split where all of them are no bigger than required without further splitting the elements. If that is the case, and it still makes no difference in speed, then maybe we are pretty much as good as we are going to get. ..Steve