About the book

  • Cover (3rd ed.)
  • Table of contents (3rd ed.)
  • Errata (1st ed.)
  • Errata (2nd ed.)
  • Order

    Implementation

  • CGAL
  • LEDA

    Further reading

  • Books

    Comments to

    geobook@cs.uu.nl

    Last modified
    Feb 14, 2008

    • Computational Geometry: Algorithms and Applications

    Third Edition (March 2008)

    Mark de Berg, TU Eindhoven (the Netherlands)
    Otfried Cheong, KAIST (Korea)
    Marc van Kreveld, Mark Overmars, Utrecht University (the Netherlands)

    published by Springer-Verlag

    3rd rev. ed. 2008. 386 pages, 370 fig.
    Hardcover approx. EUR 35,-
    ISBN: 978-3-540-77973-5

    You can order the book here.

    Download

  • Introduction (Chapter 1, pdf)
  • Delaunay Triangulations (Chapter 9, pdf)
  • All figures (a pdf for each chapter, zip)
  • All pseudocode (on separate pages, pdf)

    About the third edition

    This third edition contains two major additions: In Chapter 7, on Voronoi diagrams, we now also discuss Voronoi diagrams of line segments and farthest-point Voronoi diagrams. In Chapter 13, we have included an extra section on binary space partition trees for low-density scenes, as an introduction to realistic input models. In addition, a large number of small and some larger errors have been corrected (see the list of errata for the second edition on the Web site). We have also updated the notes and comments of every chapter to include references to recent results and recent literature. We have tried not to change the numbering of sections and exercises, so that it should be possible for students in a course to still use the second edition.

    The pages are almost square with a large margin containing over 370 figures. To get an idea about the style and format, take a look at Chapter 1, the Introduction or Chapter 9 on Delaunay triangulations.

    Computational geometry

    Computational geometry emerged from the field 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 field 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 difficult to understand and implement. In recent years a number of new algorithmic techniques have been developed that improved and simplified 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.

    Structure of the book

    Each of the sixteen chapters, except the introductory chapter, starts with a problem arising in one of the application domains. This problem is then transformed into a purely geometric one, which is solved using techniques from computational geometry. The geometric problem and the concepts and techniques needed to solve it are the real topic of each chapter. The choice of the applications was guided by the topics in computational geometry we wanted to cover; they are not meant to provide a good coverage of the application domains. The purpose of the applications is to motivate the reader; the goal of the chapters is not to provide ready-to-use solutions for them. Having said this, we believe that knowledge of computational geometry is important to solve geometric problems in application areas efficiently. We hope that our book will not only raise the interest of people from the algorithms community, but also from people in the application areas.

    For most geometric problems treated we give just one solution, even when a number of different solutions exist. In general we have chosen the solution that is most easy to understand and implement. This is not necessarily the most efficient solution. We also took care that the book contains a good mixture of techniques like divide-and-conquer, plane sweep, and randomized algorithms. We decided not to treat all sorts of variations to the problems; we felt it is more important to introduce all main topics in computational geometry than to give more detailed information about a smaller number of topics.

    Further reading

    Every chapter concludes with a section entitled Notes and Comments. These sections indicate where the results described in the chapter originated, mention other solutions, generalizations and improvements, and they provide references. They can be skipped, but do contain useful material for those who want to know more about the topic of the chapter.

    Exercises

    At the end of each chapter a number of exercises is provided. These range from easy tests to check whether the reader understands the material to more elaborate questions that extend the material covered.

    Intended audience

    The book can be used as a textbook for a high-level undergraduate course or a low-level graduate course, depending on the rest of the curriculum. Readers are assumed to have a basic knowledge of the design and analysis of algorithms and data structures: they should be familiar with big-Oh notation and simple algorithmic techniques like sorting, binary search, and balanced search trees. No knowledge of the application domains is required, and hardly any knowledge of geometry. The analysis of the randomized algorithms uses some very elementary probability theory.

    Back cover text on the third edition

    This well-accepted introduction to computational geometry is a textbook for high-level undergraduate and low-level graduate courses. The focus is on algorithms and hence the book is well suited for students in computer science and engineering. Motivation is provided from the application areas: all solutions and techniques from computational geometry are related to particular applications in robotics, graphics, CAD/CAM, and geographic information systems. For students this motivation will be especially welcome. Modern insights in computational geometry are used to provide solutions that are both efficient and easy to understand and implement. All the basic techniques and topics from computational geometry, as well as several more advanced topics, are covered. The book is largely self-contained and can be used for self-study by anyone with a basic background in algorithms.

    In this third edition, 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.