Skip to main content
SpringerLink
Log in
Book cover

Computational Geometry

Algorithms and Applications

  • Textbook
  • © 2008

Overview

Authors:
  1. Mark Berg

    1. Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, The Netherlands

    View author publications

    You can also search for this author in PubMed   Google Scholar

  2. Otfried Cheong

    1. Department of Computer Science, KAIST, Daejeon, Korea

    View author publications

    You can also search for this author in PubMed   Google Scholar

  3. Marc Kreveld

    1. Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands

    View author publications

    You can also search for this author in PubMed   Google Scholar

  4. Mark Overmars

    1. Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands

    View author publications

    You can also search for this author in PubMed   Google Scholar

  • A broad overview of the major algorithms and data structures of the field
  • Motivated from applications
  • Covers concepts and techniquesto be presented in any course on computational geometry
  • Self-contained and illustrated with 370 figures
  • Additional online material available under http://www.cs.uu.nl/geobook/
  • Besides revisions to the second edition, new sections discussing Voronoi diagrams of line segments, farthest-point Voronoi diagrams, and realistic input models have been added
  • Includes supplementary material: sn.pub/extras

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book USD 54.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (16 chapters)

  1. Front Matter

    Pages i-xii
    Download chapter 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
    Download chapter PDF
Back to top

Keywords

About this book

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.

Reviews

"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

Authors and Affiliations

  • 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

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation