|optimal partition into cartesian products? wendt@.cs.colostate.edu (1991-06-11)|
|Re: optimal partition into cartesian products? sbloch@euler.UCSD.EDU (1991-06-12)|
|From:||sbloch@euler.UCSD.EDU (Steve Bloch)|
|Organization:||Mathematics @ UCSD|
|Date:||12 Jun 91 14:46:15 GMT|
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.
Return to the
Search the comp.compilers archives again.