From: Jeff Erickson Newsgroups: comp.theory,rec.games.abstract,rec.puzzles,sci.math Subject: Re: Chopping rectangles (PROBLEM) Date: Sun, 07 Dec 1997 18:19:14 -0500 Yann DAVID wrote: > Given two rectangles A and B of equal area, is it always possible > to cut A in finitely many pieces and to use them to tile B ? Yes. This has been known since the 1700's. Think "torus". Moreover, for any two polygons X abd Y of equal area, there is a finite set of pieces that can be assembled into either X or Y. Hint: every polygon can be borken into triangles. See Greg Frederickson's marvelous new book "Dissections: Plane and Fancy" for (MANY) further details. -- Jeff Erickson Center for Geometric Computing jeffe@cs.duke.edu Department of Computer Science http://www.cs.duke.edu/~jeffe Duke University ============================================================================== From: shamos@ix.netcom.com (Michael Ian Shamos) Newsgroups: comp.theory,rec.games.abstract,rec.puzzles,sci.math Subject: Re: Chopping rectangles (PROBLEM) Date: 7 Dec 1997 21:35:16 GMT In Yann DAVID <100552.1400@CompuServe.COM> writes: >Given two rectangles A and B of equal area, is it always possible to >cut A in finitely many pieces and to use them to tile B ? Answer: yes. In 1924, Tarksi proved that any two plane polygons are finitely equidecomposable iff they have equal areas. They need not have the same number of sides. It is also known that a square and a circle of equal area are finitely equidecomposable, but the latter construction requires about 10^50 pieces. For polygons it's much simpler. Are you interested in minimizing the number of pieces or the time required to perform the decomposition (or something else)? Mike Shamos School of Computer Science Carnegie Mellon University ============================================================================== [The "pieces" in the circle decomposition have to be nonmeasurable. See 97/51ddecomp --djr] ==============================================================================