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?

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.