3
$\begingroup$

The question Algorithm for finding the fewest rectangles to cover a set of rectangles was already answered here and a similar question was answered here. Those questions were about regular geometric rectangles, where the coordinates are continuous and form an order.

Is it possible to generalize the problem, such that instead of rectangles we use cartesian products of two sets, where each set is a subset of one axis. This axes themselves should not be continuous but finite sets. These products would look more like a "grid" than a rectangle.

enter image description here

My actual problem is finding a minimal representation for a function a->b->Bool, but I believe this is equivalent to finding a minimal representation for a set of points (correct me if I'm wrong)

Should it not be possible to find a minimal set of cartesian products, is it possible to find a "good enough" solution?

$\endgroup$
2
  • $\begingroup$ You should define the problem in a precise and self-contained form. For example, it is not at all clear to me whether you want a partition or a covering. Also, are you the same Martin as this one? mathoverflow.net/questions/107830 $\endgroup$
    – domotorp
    Dec 29, 2015 at 15:54
  • $\begingroup$ I'll make it clear that I mean a partitioning. That other Martin is not me. $\endgroup$ Dec 30, 2015 at 21:52

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.