Compressing sets of rectangles... help me find an algorithm?
keefe: The first question I have is : am I correct to infer that the set of rectangles must be a subset of the original rectangles? In other words, it is not sufficient to simply generate an arbitrary set of rectangles.Finding a minimum set of rectangles to cover a particular space can be a tricky problem, I worked on rectangularization of dose curves in radiosurgery and under certain (restrictive) error conditions, finding a minimum set of rectangles to cover an x-monotone curve can actually reduce to an NP complete problem (k-MCST). I suspect your error cases are not that restrictive.Just off the top of my head, the first thing this reminds me of is the convex hull problem as described here http://en.wikipedia.org/wiki/Convex_hull where the gift wrapping algorithm is a pretty good solution. If you take each corner point of a rectangle and each intersection point of any two sides of a rectangle as an input to the convex hull, this will generate a set of points on the boundary which are required for your covering. If original rectangles are required, any rectangle with a point in the convex hull is required. This generates a set of required rectangles, you could then remove these from your set and repeat, maybe? Similarly rectangles incident on holes in the polygon formed by the gift wrapping algorithm would be required. I think that's not exactly perfectly right, but is a general approach that should work with some tweaks.If original rectangles are not required, compute the convex hull of corner points and intersections and include any holes, then you have a polygon and you need to decompose it into rectangles, that's a well known problem.This also bears some similarity to the skyline problem http://acm.uva.es/p/v1/105.html which uses a plane sweeping technique that is very similar to the gift wrapping approach for convex hull.I'm not really sure I understand the color restriction, that strikes me as potentially complicating because of the similarity to graph coloring...OK I could probably keep running my mouth about this kind of topic all day so I am going to get back to bug fixing... if that is at all helpful and you need more detail I can try to provide itEDIT : http://en.wikipedia.org/wiki/Convex_hull_algorithms There's a list of algorithms for finding the hull, perhaps a modification of the divide and conquer technique http://www.cse.ohio-state.edu/~gurari/course/cse693s04/cse69... would let you get your coloring constraints in? OK, I have to get out of this thread and back to work (: