资源描述：
《computational geometry methods and applications》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、ComputationalGeometry:MethodsandApplicationsJianerChenComputerScienceDepartmentTexasA&MUniversityFebruary19,1996Chapter1IntroductionGeometricobjectssuchaspoints,lines,andpolygonsarethebasisofabroadvarietyofimportantapplicationsandgiverisetoaninterestingsetofproblemsandalgorith
2、ms.Thenamegeometryremindsusofitsearliestuse:forthemeasurementoflandandmaterials.Today,computersarebeingusedmoreandmoretosolvelarger-scalegeometricproblems.Overthepasttwodecades,asetoftoolsandtechniqueshasbeendevelopedthattakesadvantageofthestructureprovidedbygeometry.Thisdisci
3、plineisknownasComputationalGeometry.Thedisciplinewasnamedandlargelystartedaround1975byShamos,whosePh.D.thesisattractedconsiderableattention.Afteradecadeofdevel-opmentthe eldcameintoitsownin1985,whenthreecomponentsofanyhealthydisciplinewererealized:atextbook,aconference,andajou
4、rnal.PreparataandShamos'sbookComputationalGeometry:AnIntroduction[23],the rsttextbooksolelydevotedtothetopic,waspublishedataboutthesametimeasthe rstACMSymposiumonComputationalGeometrywasheld,andjustpriortothestartofanewSpringer-VerlagjournalDiscreteandComputationalGeometry.The
5、 eldiscurrentlythriving.Since1985,sev-eraltexts,collections,andmonographshaveappeared[1,10,18,20,25,26].Theannualsymposiumhasattracted100papersand200attendeessteadily.Thereisevidencethatthe eldisbroadeningtotouchgeometricmodelingandgeometrictheoremproving.Perhapsmostimportantl
6、y,the rststudentswhoobtainedtheirPh.D.sincomputersciencewiththesesincomputationalgeometryhavegraduated,obtainedpositions,andarenowtrainingthenextgenerationofresearchers.ComputationalgeometryisofpracticalimportancebecauseEuclidean12INTRODUCTIONspaceoftwoandthreedimensionsformst
7、hearenainwhichrealphysicalobjectsarearranged.Alargenumberofapplicationsareassuchaspaternrecognition[28],computergraphics[19],imageprocessing[22],operationsresearch,statistics[4,27],computer-aideddesign,robotics[25,26],etc.,havebeentheincubationbedofthedisciplinesincetheyprovid
8、einherentlygeo-metricproblemsforwhichecientalgorithmshavetob
