首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Hinged dissection of polyominoes and polyforms
Authors:Erik D Demaine  Martin L Demaine  David Eppstein  Greg N Frederickson  Erich Friedman  
Institution:

aMIT Computer Science and Artificial Intelligence Laboratory, 32 Vassar St., 200 Technology Square, Cambridge, MA 02139, USA

bDepartment of Information and Computer Science, University of California, Irvine, CA 92697, USA

cDepartment of Computer Sciences, Purdue University, West Lafayette, IN 47907-1398, USA

dMathematics Department, Stetson University, DeLand, FL 32720, USA

Abstract:A hinged dissection of a set of polygons S is a collection of polygonal pieces hinged together at vertices that can be rotated into any member of S. We present a hinged dissection of all edge-to-edge gluings of n congruent copies of a polygon P that join corresponding edges of P. This construction uses kn pieces, where k is the number of vertices of P. When P is a regular polygon, we show how to reduce the number of pieces to left ceilingk/2right ceiling(n−1). In particular, we consider polyominoes (made up of unit squares), polyiamonds (made up of equilateral triangles), and polyhexes (made up of regular hexagons). We also give a hinged dissection of all polyabolos (made up of right isosceles triangles), which do not fall under the general result mentioned above. Finally, we show that if P can be hinged into Q, then any edge-to-edge gluing of n congruent copies of P can be hinged into any edge-to-edge gluing of n congruent copies of Q.
Keywords:Dissection  Equidecomposability  Hinging  Folding  Reconfiguration
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号