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.