Ian Mallett wrote:
I mean this in a fundamental, mathematical sense. With O(n) rectangles, you can produce O(n^2) regions that cannot be decomposed into fewer than O(n^2) disjoint rectangles.
True, but that's a worst case, unlikely to be approached in practice. Also, for this application, there will be some minimum size of rectangle below which the overhead of decomposing it further would be a net loss. If you stop at that point, there will be an upper bound on the number of rectangles you're dealing with. -- Greg
