5 ms·
Ask HN: Compressing sets of rectangles... help me find an algorithm?
I'm looking for a fast way to do the following: given a set of rectangles in the plane, return a minimal set of rectangles that covers exactly the same space.
By "minimal" I mean "having the fewest number of rectangles". However, it's more important that the algorithm be fast, so it's ok to approximate the smallest set if that would speed things up.
A variation, if that's too easy, is to introduce color: given a set of colored rectangles, return a minimal set of rectangles that covers exactly the same space, with the restriction that no rectangle can include regions that have different colors.
This feels like the kind of thing there must be standard work on (image compression?), so I've probably been searching in the wrong places. Do any of you guys have ideas about the problem and/or pointers about where to find relevant work? Thanks!
- frossie 17y agoIf I understood the question correctly... you want to Google for "minimum rectangular covering" eg. http://www.springerlink.com/content/d707j4x7107qq362/ http://www.springerlink.com/content/d707j4x7107qq362/ Disclaimer: IANAMathematician
- gruseom 17y agoThat search term digs up some stuff I hadn't seen before that might be applicable. The particular paper you mentioned starts with a polygon rather than a set of rectangles, though.
- tlb 17y agoI think Cairo, the graphics rendering library keeps an internal data structure that's the set of overlapping filled regions and updates it with and/or/xor operators.
- gruseom 17y agoThanks. Perhaps I'll ask about this on their mailing list.
- jdoliner 17y agoWell if you're willing to sacrifice a bit of speed I think I have a pretty good heuristic algorithm you can use: Step 1: Find a maximal point, by this a mean a point `p' s.t. no point has x >= p.x and y >= p.y. (such a point clearly exists). Step 2: Now it shouldn't be too hard to see that for a rectangle to cover `p' it would have to have `p' as one of its corners, so we set one corner as `p' and then grow the other corner until it runs into walls. This is just off the top of my head so I'm haven't really done much analysis. You could make it a bit slower and actually get the rectangle that takes up the most area instead of just growing until you hit walls. Not sure how much that actually improves it.
- gruseom 17y agoThis raises the question of exactly how to grow the rectangles, i.e. how to pick out the ones that have adjacent space to consume, what to do with the leftovers after a merge (since the union of two rectangles may not be a rectangle) and so on. It's too slow to examine all the rectangles every time you want to answer one of these questions, so you need a way of arranging them. I've written code that is vaguely similar to what you suggest (but is too slow). It sorts the rectangles in one x-coordinate and then one y-coordinate, which still leaves a lot of searching to do. Perhaps keeping four sorted lists of the rectangles would help, but that's costly too, since as you coalesce rectangles you need to insert and delete from the set.
- mikhailfranco 17y agoSearch for R-Tree and the many variants used for spatial indexing. You will find the papers very pragmatic about the tradeoffs between optimal coverage and speed of creation, update and traversal. Parallelizing with transactional guarantees is still a bit of a research topic. It would be interesting to do some experimental implementations in, say, Erlang.
- gruseom 17y agoWe've actually been deep into R-trees, and I wrote an Rstar-tree recently, but the problem posted above, of coalescing adjacent rectangles that have some sort of affinity (e.g. same color), doesn't appear in the R-tree literature I've read so far. Probably you could do it using neighbor queries and remove/reinsert, but this is probably too slow. If you have any further suggestions along these lines, do please post them.
- keefe 17y agoThe 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 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 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 it EDIT : http://en.wikipedia.org/wiki/Convex_hull_algorithms 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/cse693s04su85.html 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 (:
- gruseom 17y ago