5 ms·

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 sufficien

by keefe 17y ago

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 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
Original rectangles are not required. What's important is only that the new rectangles cover the exact same portions of the plane as the original rectangles. This rules out computing the convex hull and then decomposing, because that would fill in any holes, i.e. the new rectangles would be covering space that the old rectangles didn't cover, which won't work. Maybe I can explain this more fully. We are doing computationally-intensive processing of different regions of the plane. The order in which the regions get processed is unpredictable. We need to quickly, precisely and compactly answer the question: "which regions have been processed so far"? Suppose you hire a guy to paint your wall. He's very anal (or, let's be modern about it, has Asperger's) and only ever paints in axis-parallel rectangles. He's easily distracted and liable to paint rectangles in arbitary locations, so the process doesn't proceed in any linear way, but he does cover the wall eventually. Paint is expensive, so you instruct him never to paint over the same area twice. Our problem is to efficiently answer the question, "What portions of the wall have been painted so far?" Obviously we could just keep a list and add each new rectangle as it gets painted. But as the wall gets filled in, many painted areas will blend together. We'd like to keep the list as small as possible, i.e. we want the painted-so-far rectangles to be as large as possible. If we didn't care about that, we could just divide the wall into pixels and track the state of each. It's not a disaster if we paint a few spots twice, but it's really bad to mark an area as painted if it hasn't been. That's why we can't ignore holes in the bounding polygon, i.e. space between painted rectangles. (Edit: actually no, it is bad if we paint the same spot twice. Imagine that the paint explodes if you do that. :)) The painting analogy can be extended to include color. In the original problem, we're painting the wall with a single color and all we care about is painted vs. not-painted. But if we introduce multiple colors, then we want to track not just "which areas are painted" but "which areas are painted blue and which areas are painted yellow". We still want to answer that question with as few rectangles as possible, but now we're not allowed to merge blue areas with yellow areas. That being said, a non-color solution would get us a long way. NP complete problems are found everywhere in this space, no question about it. But there are also often useful results around approximations and heuristics. We don't need the optimal set, just small enough to make what we're doing fast. Edit: the above also sheds light on why spatial indexing structures like R-trees don't work for this out of the box (though maybe they can be adapted to do so). These structures let you add rectangles and find them again. But they don't merge rectangles. If our painter takes a fancy to one-centimeter squares and decides to paint a thousand of them all in a row, an R-tree would end up with a thousand rectangles, even though the total painted area is a single n-by-1 rectangle at every step. Something like an R-tree with a "compaction" phase would be close to what we need, but maybe not close enough, because insertion into an R-tree is expensive.

by keefe 17y ago

gruseom 17y ago

Original rectangles are not required. What's important is only that the new rectangles cover the exact same portions of the plane as the original rectangles. This rules out computing the convex hull and then decomposing, because that would fill in any holes, i.e. the new rectangles would be covering space that the old rectangles didn't cover, which won't work. Maybe I can explain this more fully. We are doing computationally-intensive processing of different regions of the plane. The order in which the regions get processed is unpredictable. We need to quickly, precisely and compactly answer the question: "which regions have been processed so far"? Suppose you hire a guy to paint your wall. He's very anal (or, let's be modern about it, has Asperger's) and only ever paints in axis-parallel rectangles. He's easily distracted and liable to paint rectangles in arbitary locations, so the process doesn't proceed in any linear way, but he does cover the wall eventually. Paint is expensive, so you instruct him never to paint over the same area twice. Our problem is to efficiently answer the question, "What portions of the wall have been painted so far?" Obviously we could just keep a list and add each new rectangle as it gets painted. But as the wall gets filled in, many painted areas will blend together. We'd like to keep the list as small as possible, i.e. we want the painted-so-far rectangles to be as large as possible. If we didn't care about that, we could just divide the wall into pixels and track the state of each. It's not a disaster if we paint a few spots twice, but it's really bad to mark an area as painted if it hasn't been. That's why we can't ignore holes in the bounding polygon, i.e. space between painted rectangles. (Edit: actually no, it is bad if we paint the same spot twice. Imagine that the paint explodes if you do that. :)) The painting analogy can be extended to include color. In the original problem, we're painting the wall with a single color and all we care about is painted vs. not-painted. But if we introduce multiple colors, then we want to track not just "which areas are painted" but "which areas are painted blue and which areas are painted yellow". We still want to answer that question with as few rectangles as possible, but now we're not allowed to merge blue areas with yellow areas. That being said, a non-color solution would get us a long way. NP complete problems are found everywhere in this space, no question about it. But there are also often useful results around approximations and heuristics. We don't need the optimal set, just small enough to make what we're doing fast. Edit: the above also sheds light on why spatial indexing structures like R-trees don't work for this out of the box (though maybe they can be adapted to do so). These structures let you add rectangles and find them again. But they don't merge rectangles. If our painter takes a fancy to one-centimeter squares and decides to paint a thousand of them all in a row, an R-tree would end up with a thousand rectangles, even though the total painted area is a single n-by-1 rectangle at every step. Something like an R-tree with a "compaction" phase would be close to what we need, but maybe not close enough, because insertion into an R-tree is expensive.