Skip to main content
SpringerLink
Log in
Book cover
  • Textbook
  • © 2000

Computational Geometry

Algorithms and Applications

Authors:

  1. Mark Berg

    1. Department of Computer Science, TU Eindhoven, Eindhoven, the Netherlands

    View author publications

    You can also search for this author in PubMed   Google Scholar

  2. Marc Kreveld

    1. Department of Computer Science, Utrecht University, Utrecht, The Netherlands

    View author publications

    You can also search for this author in PubMed   Google Scholar

  3. Mark Overmars

    1. Department of Computer Science, Utrecht University, Utrecht, The Netherlands

    View author publications

    You can also search for this author in PubMed   Google Scholar

  4. Otfried Cheong Schwarzkopf

    1. Department of Computer Science, 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
  • Self-contained and illustrated with 370 figures
  • 2nd edition comes with new exercises and larger revisions in chapters 4 and 7
  • Includes supplementary material: sn.pub/extras

Sections

Buy it now

eBook USD 74.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever

Tax calculation will be finalised at checkout

Other ways to access

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

Table of contents (16 chapters)

  1. Front Matter

    Pages i-xii
    PDF

  2. Computational Geometry

    • Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong Schwarzkopf
    Pages 1-17

  3. Line Segment Intersection

    • Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong Schwarzkopf
    Pages 19-43

  4. Polygon Triangulation

    • Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong Schwarzkopf
    Pages 45-61

  5. Linear Programming

    • Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong Schwarzkopf
    Pages 63-94

  6. Orthogonal Range Searching

    • Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong Schwarzkopf
    Pages 95-120

  7. Point Location

    • Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong Schwarzkopf
    Pages 121-146

  8. Voronoi Diagrams

    • Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong Schwarzkopf
    Pages 147-163

  9. Arrangements and Duality

    • Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong Schwarzkopf
    Pages 165-182

  10. Delaunay Triangulations

    • Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong Schwarzkopf
    Pages 183-210

  11. More Geometric Data Structures

    • Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong Schwarzkopf
    Pages 211-233

  12. Convex Hulls

    • Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong Schwarzkopf
    Pages 235-250

  13. Binary Space Partitions

    • Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong Schwarzkopf
    Pages 251-265

  14. Robot Motion Planning

    • Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong Schwarzkopf
    Pages 267-290

  15. Quadtrees

    • Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong Schwarzkopf
    Pages 291-306

  16. Visibility Graphs

    • Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong Schwarzkopf
    Pages 307-317

  17. Simplex Range Searching

    • Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong Schwarzkopf
    Pages 319-339

  18. Back Matter

    Pages 341-367
    PDF
Back to top

About this book

Computational geometry emerged from the field of algorithms design and anal­ ysis in the late 1970s. It has grown into a recognized discipline with its own journals, conferences, and a large community of active researchers. The suc­ cess 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 in­ formation systems (GIS), robotics, and others-in which geometric algorithms playafundamental 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 modem 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.
Back to top

Keywords

Back to top

Authors and Affiliations

  • Department of Computer Science, TU Eindhoven, Eindhoven, the Netherlands

    Mark Berg

  • Department of Computer Science, Utrecht University, Utrecht, The Netherlands

    Marc Kreveld, Mark Overmars, Otfried Cheong Schwarzkopf

Back to top

Bibliographic Information

Back to top

Publish with us

Policies and ethics

Back to top
Access via your institution

Buy it now

eBook USD 74.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever

Tax calculation will be finalised at checkout

Other ways to access

Search

Navigation