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?