I have a set of $n$, $d$-dimensional hyperrectangles which may be overlapping in arbitrary ways. I would like to partition the area covered by this set into a set of non-overlapping hyperrectangles. I am not sure of the hardness of this problem, so first and foremost I am interested in any correct algorithm; any notions of optimality would be a bonus.
This problem is related to, may be a special case of or identical to the problem of finding a rectangular covering of a rectilinear polygon, as discussed in the answer to another stack overflow question. One difference is that I am interested in the $n$, not 2 dimensions, and I am unsure of how their results generalise. Secondly, I am starting not with an arbitrary orthogonal polyhedron, but with a set of orthotopes of known dimensions; hopefully this will make it easier.
Best Answer
Perhaps explore using a Binary Space Partition (BSP). Here are two papers on the topic, from which you can reach more. (Google scholar lists 26 papers that cite the 2001 paper below.)
(Image from euclideanspace.com.)
In response to the zenna's comment, here is another reference that specifically explores cutting overlapping hyperrectangles by "balanced cuts," cuts which can then be employed by a BSP algorithm.