2

I have a set of 2D points. I want to find a set of (possibly overlapping and arbitrarily oriented) bounding-boxes for subsets of these points such that each point lies within at least one box, each box contains at least k points and such that the combined area of the boxes is minimized.

One idea for an algorithm I have is:

  • use a concave-hull algorithm to find a concave hull for the points.
  • use convex decomposition algorithm to find a set of convex hulls.
  • compute arbitrarily oriented minimum bounding box for each of the convex hulls.

I'm looking for a list of other (potentially better suited) algorithms for this problem?

matthias_buehlmann
  • 4,641
  • 6
  • 34
  • 76
  • Have you considered using some variant of the k-means algorithm? K-means minimizes the mean square distances from the center points of each cluster and not the bounding boxes. Furthermore, standard k-means does not allow you to specify a minimum point number per cluster. Still I think that, depending on your data, it could be a good starting point to find an approximate solution. – Frank Puffer Jan 31 '20 at 16:35
  • does this answer? https://stackoverflow.com/questions/60401171/how-can-i-find-k-minimum-bounding-rectangles-to-enclose-all-the-given-points – Jean-François Fabre Feb 28 '20 at 20:56

0 Answers0