This challenge to identify good sets that avoid empty sets seems similar to the k-means clustering problem. I wonder if this (or other similar machine learning approaches) could be used to generate better bounding boxes.
@shadaj I think it's a great idea. Actually I found a paper relating to applying k-means to draw bounding boxes for BVH. Specifically, they use k-means to subdivide scene primitives into clusters. From these clusters they construct treelets using the agglomerative clustering algorithm. Find the link to the paper here: http://watkins.cs.queensu.ca/~jstewart/454/notes/bvh_construction.pdf