Computational Geometry

1. Front Matter

   Pages i-xii

   PDF

2. Computational Geometry

   Pages 1-17

3. Line Segment Intersection

   Pages 19-43

4. Polygon Triangulation

   Pages 45-61

5. Linear Programming

   Pages 63-93

6. Orthogonal Range Searching

   Pages 95-120

7. Point Location

   Pages 121-146

8. Voronoi Diagrams

   Pages 147-171

9. Arrangements and Duality

   Pages 173-190

10. Delaunay Triangulations

    Pages 191-218

11. More Geometric Data Structures

    Pages 219-241

12. Convex Hulls

    Pages 243-258

13. Binary Space Partitions

    Pages 259-281

14. Robot Motion Planning

    Pages 283-306

15. Quadtrees

    Pages 307-322

16. Visibility Graphs

    Pages 323-333

17. Simplex Range Searching

    Pages 335-355

18. Back Matter

    Pages 357-386

    PDF

Computational geometry emerged from the ?eld of algorithms design and analysis in the late 1970s. It has grown into a recognized discipline with its own journals, conferences, and a large community of active researchers. The success of the ?eld as a research discipline can on the one hand be explained from the beauty of the problems studied and the solutions obtained, and, on the other hand, by the many application domains—computer graphics, geographic information systems (GIS), robotics, and others—in which geometric algorithms play a fundamental role. For many geometric problems the early algorithmic solutions were either slow or dif?cult to understand and implement. In recent years a number of new algorithmic techniques have been developed that improved and simpli?ed many of the previous approaches. In this textbook we have tried to make these modern algorithmic solutions accessible to a large audience. The book has been written as a textbook for a course in computational geometry,but it can also be used for self-study.

• Area
• CAM
• Partition
• Triangulation
• algorithm
• algorithms
• computer science
• data structure
• data structures
• database
• information
• linear optimization
• programming
• robot
• robotics
• algorithm analysis and problem complexity

"An excellent introduction to the field is given here, including a general motivation and usage cases beyond simple graphics rendering or interaction." from the ACM Reviews by William Fahle, University of Texas at Dallas, USA

• Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, The Netherlands

  Mark Berg

• Department of Computer Science, KAIST, Daejeon, Korea

  Otfried Cheong

• Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands

  Marc Kreveld, Mark Overmars

Policies and ethics