Geometric-Folding-Algorithms.-折叠算法

P1:FYX/FYXP2:FYX0521857570preCUNY758/Demaine0521810957February25,20077:5GEOMETRICFOLDINGALGORITHMSFoldingandunfoldingproblemshavebeenimplicitsinceAlbrechtDürerintheearly1500sbuthaveonlyrecentlybeenstudiedinthemathemat-icalliterature.Overthepastdecade,therehasbeenasurgeofinterestintheseproblems,withapplicationsrangingfromroboticstoproteinfolding.Withanemphasisonalgorithmicorcomputationalaspects,thiscomprehensivetreatmentofthegeometryoffoldingandunfoldingpresentshundredsofresultsandmorethan60unsolved“openprob-lems”tospurfurtherresearch.Theauthorscoverone-dimensional(1D)objects(linkages),2Dobjects(paper),and3Dobjects(polyhedra).AmongtheresultsinPartIisthatthereisaplanarlinkagethatcantraceoutanyalgebraiccurve,even“signyourname.”PartIIfeaturesthe“fold-and-cut”algorithm,establishingthatanystraight-linedrawingonpapercanbefoldedsothatthecom-pletedrawingcanbecutoutwithonestraightscissorscut.InPartIII,readerswillseethatthe“Latincross”unfoldingofacubecanberefoldedto23differentconvexpolyhedra.Aimedprimarilyatadvancedundergraduateandgraduatestudentsinmathematicsorcomputerscience,thislavishlyillustratedbookwillfascinateabroadaudience,fromhighschoolstudentstoresearchers.ErikD.DemaineistheEstherandHaroldE.EdgertonProfessorofElec-tricalEngineeringandComputerScienceattheMassachusettsInstituteofTechnology,wherehejoinedthefacultyin2001.Heistherecipientofseveralawards,includingaMacArthurFellowship,aSloanFellowship,theHaroldE.EdgertonFacultyAchievementAward,theRuthandJoelSpiraAwardforDistinguishedTeaching,andtheNSERCDoctoralPrize.Hehaspublishedmorethan150paperswithmorethan150collabora-torsandcoeditedthebookTributetoaMathemagicianinhonoroftheinfluentialrecreationalmathematicianMartinGardner.JosephO’RourkeistheOlinProfessorofComputerScienceatSmithCollegeandthefoundingChairoftheComputerScienceDepartment.Hehasreceivedseveralgrantsandawards,includingaPresidentialYoungInvestigatorAward,aGuggenheimFellowship,andtheNSFDirector’sAwardforDistinguishedTeachingScholars.Hisresearchisinthefieldofcomputationalgeometry,wherehehaspublishedamonographandatextbook,andcoeditedtheHandbookofDiscreteandComputationalGeometry.iP1:FYX/FYXP2:FYX0521857570preCUNY758/Demaine0521810957February25,20077:5GeometricFoldingAlgorithmsLinkages,Origami,PolyhedraERIKD.DEMAINEMassachusettsInstituteofTechnologyJOSEPHO’ROURKESmithCollegeiiiP1:FYX/FYXP2:FYX0521857570preCUNY758/Demaine0521810957February25,20077:5cambridgeuniversitypressCambridge,NewYork,Melbourne,Madrid,CapeTown,Singapore,SãoPauloCambridgeUniversityPress32AvenueoftheAmericas,NewYork,NY10013-2473,USAErikD.Demaine,JosephO’Rourke2007Thispublicationisincopyright.Subjecttostatutoryexceptionandtotheprovisionsofrelevantcollectivelicensingagreements,noreproductionofanypartmaytakeplacewithoutthewrittenpermissionofCambridgeUniversityPress.Firstpublished2007PrintedintheUnitedStatesofAmericaAcatalogrecordforthispublicationisavailablefromtheBritishLibrary.LibraryofCongressCataloginginPublicationDataDemaine,ErikD.,1981–Geometricfoldingalgorithms:linkages,origami,polyhedra/ErikD.Demaine,JosephO’Rourke.p.cm.Includesindex.ISBN-13:978-0-521-85757-4(hardback)ISBN-10:0-521-85757-0(hardback)1.Polyhedra–Models.2.Polyhedra–Dataprocessing.I.O’Rourke,Joseph.II.Title.QA491.D462007516.156–dc222006038156ISBN978-0-521-85757-4hardbackCambridgeUniversityPresshasnoresponsibilityforthepersistenceoraccuracyofURLsforexternalorthird-partyInternetWebsitesreferredtointhispublicationanddoesnotguaranteethatanycontentonsuchWebsitesis,orwillremain,accurateorappropriate.ivP1:FYX/FYXP2:FYX0521857570preCUNY758/Demaine0521810957February25,20077:5Tomyfather,MartinDemaineTomymother,EleanorO’Rourke–Erik–JoevP1:FYX/FYXP2:FYX0521857570preCUNY758/Demaine0521810957February25,20077:5ContentsPrefacepagexi0Introduction.........................10.1DesignProblems10.2FoldabilityQuestions3PartI.Linkages1ProblemClassificationandExamples............91.1Classification101.2Applications112UpperandLowerBounds.................172.1GeneralAlgorithmsandUpperBounds172.2LowerBounds223PlanarLinkageMechanisms................293.1Straight-lineLinkages293.2Kempe’sUniversalityTheorem313.3Hart’sInversor404RigidFrameworks.....................434.1BriefHistory434.2Rigidity434.3GenericRigidity444.4InfinitesimalRigidity494.5Tensegrities534.6PolyhedralLiftings575ReconfigurationofChains.................595.1ReconfigurationPermittingIntersection595.2ReconfigurationinConfinedRegions675.3ReconfigurationwithoutSelf-Crossing706LockedChains.......................866.1Introduction866.2History87viiP1:FYX/FYXP2:FYX0521857570preCUNY758/Demaine0521810957February25,20077:5viiiContents6.3LockedChainsin3D886.4NoLockedChainsin4D926.5LockedTreesin2D946.6NoLockedChainsin2D966.7AlgorithmsforUnlocking2DChains1056.8InfinitesimallyLockedLinkagesin2D1136.93DPolygonswithaSimpleProjection1197InterlockedChains....................1237.12-chains1257.23-chains1267.34-chains1278Joint-ConstrainedMotion.................1318.1Fixed-AngleLinkages1318.2Convex