Xref: utzoo comp.theory:2107 comp.compilers:2082
Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!ora!iecc!compilers-sender
From: sbloch@euler.UCSD.EDU (Steve Bloch)
Newsgroups: comp.theory,comp.compilers
Subject: Re: optimal partition into cartesian products?
Keywords: theory, question
Message-ID: <91-06-012@comp.compilers>
Date: 12 Jun 91 14:46:15 GMT
References: <91-06-010@comp.compilers>
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: sbloch@euler.UCSD.EDU (Steve Bloch)
Followup-To: comp.theory
Organization: Mathematics @ UCSD
Lines: 18
Approved: compilers@iecc.cambridge.ma.us

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.