Article View: comp.theory
Article #1795Re: optimal partition into cartesian products?
From: Steve Bloch
Date: Wed, 12 Jun 1991 14:46
Date: Wed, 12 Jun 1991 14:46
18 lines
1359 bytes
1359 bytes
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.
Technical Details
Message-ID:
<91-06-012@comp.compilers>Path:
arc1-ca.pugleaf.net!utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!ora!iecc!compilers-senderReferences:
<91-06-010@comp.compilers>Show Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!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