[comp.compilers] optimal partition into cartesian products?

wendt@.cs.colostate.edu (Alan Wendt) (06/12/91)

I've got a theoretical problem I'm hoping someone can give me a citation
for.  I'm trying to partition a subset of a n-dimensional cartesian product
into a miniumum number of cartesian products.  For example, if n=2,
A = {a,b,c} and B = {d,e,f}, I might have a subset {ad,bd,be,cd,ce,cf} and
I want to find the minimum # of rectangles needed to tile the triangle
in the diagram below (answer=3).  A general solution would of course allow
for arbitrary n and for moving rows and columns around in the diagram.


                a   x
                b   x x
                c   x x x
                    d e f

Alan Wendt
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.

sbloch@euler.UCSD.EDU (Steve Bloch) (06/12/91)

wendt@.cs.colostate.edu (Alan Wendt) writes:
>I'm trying to partition a subset of a n-dimensional cartesian product
>into a miniumum number of cartesian products.
>I want to find the minimum # of rectangles needed to tile the triangle
>in the diagram below (answer=3).

I seem to recall this sort of tiling problem figuring crucially in a
proof of a circuit complexity lower-bound; we used two different
numbers, with and without the requirement that the rectangles be non-
overlapping.  Unfortunately, I can't seem to find my notes from Mike
Saks' class, in which we did this.

-- 
Stephen Bloch
sbloch@math.ucsd.edu
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.