Re: optimal partition into cartesian products?

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
--

Return to the comp.compilers page.
Search the comp.compilers archives again.