# Grouping a set of rectangles in larger rectangular regions

I have a set of rectangles, which I want to cluster (group) as shown here(I can not post images yet, so please bear with me).

The approach I took was to consider central points of each rectangle as a data point in $R^2$ and cluster them using Euclidean distance (K-means, K-mediods approach or any other method). Traditional clustering approaches help you to discover shapes in data, but I am not trying to discover such shapes, as I know the best shape would be rectangles. I do not know the number of clusters (number of bounding rectangles) beforehand. However, given a clustering solution, an objective measure (BIC) can be calculated to measure clustering accuracy.

Given this situation, my question is, is there any algorithmic formulation of this or a similar problem?

• Are the rectangles in your set assumed to be disjoint? – a3nm May 22 '13 at 17:27
• yes.the original rectangles are disjoint, as well as the bigger rectangles where I want to combine them. – rivu May 22 '13 at 18:30