Creating Disjoint Sets

[pianorain]

I'm sure someone else in the world has thought a great deal about this, but my Google-foo is thwarted by not knowing what keywords to use.

One way to think about the problem: I have some number of hyperrectangles. These shapes may overlap. I want to slice up my hyperrectangles into smaller hyperrectangles such that:

1. No hyperrectangles overlap.
2. There are as few hyperrectangles as possible.

Here is a visual example in two dimensions.

I'm trying to come up with a good algorithmic way of doing this without using a ton of memory. Any suggestions for search terms or algorithms would be appreciated.

[VirtualAce]

If you extend either the vertical line segments of the inner rectangle or the horizontal lines of the inner rectangle you will always have the right number of splits. The only chore here is to determine which rectangle's edges to extend. In your 2D example the decision is trivial. Most of the algorithm would be to find which rectangle edges to extend to create more rectangles.

[Mario F.]

I was thinking along those lines.

Getting the right edges couldn't be a "simple" matter of looking for those edges inside each rectangle? You can easily check this by simply checking if any of the corners of rectangle A are located inside Rectangle B area. You'll then extend those corners in the x and y and z axis.

The only problem I see is if you allow for each rectangle to be rotated differently. I wouldn't know how to slice the rectangles if that happened. Not in 2D or 3D. You wouldn't come up with rectangles or hyperrectangles. I'm not sure how it could be handled with the Cartesian coordinates in 3D also. But maybe the polar coordinates helped?

[VirtualAce]

I'm not sure how you would find all the smaller rectangles if we are talking about two rectangles that have arbitrary rotations. That would be quite complex. However if the rectangles are always axis-aligned then the algorithm is much simpler as Mario has suggested.