On Mon, Mar 27, 2017 at 5:26 PM, Greg Ewing <greg.ew...@canterbury.ac.nz> wrote:
> Ian Mallett wrote: > >> Unfortunately, computing those rectangles is annoying, and also O(n^2) in >> the number of rectangles >> > > With the right data structures and algorithms, it doesn't have to be. > 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. Ian