计算几何（第3版）

图书标准信息

• 作者 [荷]伯格（Berg M.） 著
• 出版社 世界图书出版公司
• 出版时间 2013-10
• 版次 3
• ISBN 9787510061776
• 定价 79.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 386页
• 正文语种 英语
• 原版书名 Computational Geometry

【内容简介】

　　Computationalgeometryemergedfromthefieldofalgorithmsdesignandanalysisinthelate1970s.Ithasgrownintoarecognizeddisciplinewithitsownjoumals，conferences，andalargecommunityofactiveresearchers.Thesuccessofthefieldasaresearchdisciplinecanontheonehandbeexplainedfromthebeautyoftheproblemsstudiedandthesolutionsobtained，and，ontheotherhand，bythemanyapplicationdomains-computergraphics，geographicinformationsystems（GIS），robotics，andothers-inwhichgeometricalgonthmsplayafundamentalrole.
　　Formanygeometricproblemstheearlyalgorithmicsolutionswereeitherslowordifficulttounderstandandimplement.Inrecentyearsanumberofnewalgorithmictechruqueshavebeendevelopedthatimprovedandsimplifiedmanyofthepreviousapproaches.Inthistextbookwehavetriedtomakethesemodemalgorithmicsolutionsaccessibletoalargeaudience.Thebookhasbeenwrittenasatextbookforacourseincomputationalgeometry，butitcanalsobeusedforself-study.

【目录】

1ComputationaIGeometryIntroduction
1.1AnExample:ConvexHulls
1.2DegeneraciesandRobustness
1.3ApplicationDomains
1.4NotesandComments
1.5Exercises

2LineSegmentlntersectionThematicMapOverlay
2.1LineSegmentlntersection
2.2TheDoubly-ConnectedEdgeList
2.3ComputingtheOverlayofTwoSubdivisions
2.4BooleanOperations
2.5NotesandComments
2.6Exercises

3PolygonTriangulation
GuardinganArtGaHery
3.1GuardingandTriangulations
3.2PartitioningaPolygonintoMonotonePieces
3.3TriangulatingaMonotonePolygon
3.4NotesandComments
3.5Exercises
4LinearProgramming
ManufacturingwitbMolds
4.1TheGeometryofCasting
4.2Half-Planelntersection
4.3IncrementaILinearProgramnung
4.4RandomizedLinearProgramming
4.5UnboundedLinearPrograms
4.6*LinearProgramminginHigherDimensions
4.7*SmallestEnclosingDiscs
4.8NotesandComments
4.9Exercises
5OrthogonaIRangeSearchingQueryingaDatabase
5.1l-DimensionalRangeSearching
5.2Kd-Trees
5.3RangeTrees
5.4Higher-DimensionaIRangeTrees
5.5GeneralSetsofPoints
5.6FractionaICascading.
5.7NotesandComments
5.8Exercises
6PointLocationKnowingWhereYouAre
6.1PointLocationandTrapczoidaIMaps
6.2ARandomizedIncrementaIAlgorithm
6.3DealingwithDegenerateCases
6.4*ATaiIEstimate
6.5NotesandComments
6.6Exercises
7VoronoiDiagrams
ThePostOrfficeProblem
7.1DefinitionandBasicPtoperties
7.2ComputingtheVoronoiDiagram
7.3VoronoiDiagramsofLineSegments
7.4Farthest-PointVoronoiDiagrams
7.5NotesandComments
7.6Exercises
8ArrangementsandDualitySupersamplinginRayTracing
8.1ComputingtheDiscrepancy
8.2Duality
8.3ArrangementsofLines
8.4LevelsandDiscrepancy
……

9DelaunayTriangulationsHejghtInterpolation
10MoreGeometricDataStructuresWindowing
11ConvexHullsMixingThings
12BinarySpacePartitionsThePainter'sAlgorithm
13RobotMotionPlaruungGettingWhereYouWanttoBe
14QuadtreesNon-UruformMeshGeneration
15VisibilityGraphsFindingtheShortestRoute
16SimplexRangeSearchingWindowingRevisited
Bibliography
Index