Вариант следующий.
1) Если после наложения фигур построить контуры, образованные сторонами прямоугольников (т.е. обьединить их как бы булевскими операцими по типу 3dsmax), то количество несвязных областей будет равно количеству образовавшихся контуров. (Т.е. как бы рисуем один прямоугольник, поверх него второй, потом стираем линии там, где они попадают внутрь другого прямоугольника. Количество замкнутых линий, образованных сторонами разных прямоугольников будет равно количеству несвязных областей. Фишка в том, что надо считать только те контуры, в которых перпендикуляры, проведенные от сторон прямоугольников (наружу для прямоугольников) будут смотреть внутрь образуемого контура. Вариант надо проверять.

2) Несвязная область образуется только в том случае, если шагая от одного прямоугольника к другому через точки их наложения, можно вернуться к исходному прямоугольнику. По-идее, число несвязных областей в этом случае должно быть равно числу кратчайших путей + 1 (одна несвязная область всегд присутсвует - внешнее пространство. Это надо проверять и тестить. Вариант спорен.

3) Наиболее верный и наиболее сложный вариант - Можно попытаться дробить пространство (каждая коробочка - 4 плоскости, образующие 8 подпространств (9е внутри коробочки - игнорируем). Делаем класс пространства, у которого задан BoundingBox - те самые левый верхний и правый нижний углы. Изначально пространство +- бесконечность. В классе пространства записаны указатели на соседей слева, справа, сверху и снизу. (по диагонали не надо) Делаем процедуру "дробить" пространство. - т.е. тестим его на предмет попадания в бокс. При попадании какой-либо стороны пространства в бокс отсечения полностью (т.е. полностью попала правая сторона, левая, верхняя, нижняя, и т.д.) Удаляем указатель на бокс из соседа с той стороны, которая попала в область отсечения. В случае, если подпространство в плоскость отсечения не попадает, не меняем ничего. В случае, если оно попадает в полскость отсечения частично, то дробим пространство, обновляя списки соседей. По окончании дробления обходим все массив с пространствами, обходя соседей по одному. Автоматически получится набор сегментов, образующих подпространство. Вариант рабочий.

4) Если числа - целые, и с ограниченной точностью, довольно маленькой (256, например :)), можно нарисовать в памяти шахматную доску и битов, которую (образно) залить белым цветом, а потом черным закрашивать на ней квадратики. В дальнейшем, можно сканнировать доску в поисках белых областей и по алгоритму paint'а заливать оставшиеся белые области черной краской. Количество заливок будет равно количеству непересекающихся пространств. Вариант рабочий.

5) Пространство представляется 2D массивом. 1 элемент массива представляет одно подпространстов - либо занятое, либо нет. Есть два 1D массива, в которых записано положение плоскостей разделения по X и Y. Изначально массив 1D. При наложении бокса на пространство, массив дробится, и увеличивается в размерах. Т.е. если бокс приходится на центр массива, то массив станет 3x3, центральная клетка будет отображать пустое пространство. Если бокс придется на сторону - массив будет 3x2 или 2x3. Если на угол - то 2x2. И так далее.
После наложения боксов на пространство, массив обходится на предмет соседей. Пустые области находятся по алгоритму в пункте 4. Вариант рабочий.

ЗЫ. Ну как, понятно? :)

ПалестинецМножество прямоугольников разбиваем на классы по следующему отношению: если вершина одного находится в другом то они принадлежат одному классу.
Количество классов = количество несвязных областей.

простейший алго ~ O(N^2).
Неверно. Тут нужны непересекающиеся пространства, не занятые прямоугольниками. (Если, конечно, я правильно понял:)). Ниже корявый пример псевдографикой, для которого классов будет два, а подпространство - одно.

Палестинец (Если, конечно, я правильно понял:)).
Хм. перечитал. более вероятно что так, как-то не так условие понял сходу :-)


http://kolyanlab.k66.ru/exercises/PartV/g6_1093.html
Очень похоже на то, что я писал в третьем/пятом пункте. Только 2D генерируется более эффективно.