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 '13 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 '13 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.