12 Jun 91 14:46:15 GMT

Related articles |
---|

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

Newsgroups: | comp.theory,comp.compilers |

From: | sbloch@euler.UCSD.EDU (Steve Bloch) |

Followup-To: | comp.theory |

Keywords: | theory, question |

Organization: | Mathematics @ UCSD |

References: | 91-06-010 |

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.

--

Stephen Bloch

sbloch@math.ucsd.edu

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.