2

I'm not sure how best to describe this without using sets:

Assume we have two distinct, finite sets A & B, and a set P which contains a subset of all the different pairs of A & B (it's a predicate join, basically).

for example:

P = { (a1, b1), (a1, b3), (a2, b1), (a2, b3), (a1, b2) }

I want to find a set C which contains contains the fewest (or close to) number of pairs (as,bs) of subsets of A & B, eg:

C = { ( {a1, a2}, {b1, b3} ), ( {a1}, {b2} ) }

such that for each (as,bs) in C, for each combination of a in as and b in bs, (a,b) is in P and each element of P appears once and only once in this 'expansion' of C.

i'm not exactly sure how to describe this, but it seems somewhat analagous to rectangle covering in computational geometry. maybe someone has seen something like this before?

Spongman
  • 9,665
  • 8
  • 39
  • 58
  • Problem has some similarities with rectilinear polygon partitioning, but problem is that sets are not ordered. Check [question and answer](http://stackoverflow.com/questions/40674999/find-the-most-efficient-grouping-of-a-series-of-intervals/40703321#40703321) to similar problem where one axis is not ordered. – Ante Dec 31 '16 at 11:48

0 Answers0