Computational Geometry: Algorithms and Applications

by Mark de Berg, Otfried Cheong, Mark Overmars

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.

Genres: Computer Science, Mathematics, Programming, Textbooks, Science, Nonfiction, Algorithms

Kindle Edition

First published July 11, 1997

Reviews

[Willy Van den driessche · Rating 5 out of 5]

Beauty is the first test. This is a very beautiful book (form) with a beautiful contents. The book explains in a very throrough way some of the fundamental algoritms in "computational geometry". You will learn how to compute a convex hull for a set of points, how to determine which line segments cross in a set of line segments, how to efficiently determine which part of a set of polygons is clicked, how to compute a voronoi diagram etc... The authors take their time to explain why some algorithm is chosen and explain it with very clear and beautiful diagrams. This is a standard for all algorithmic books to come.

[Shawna · Rating 3 out of 5]

It's a great text book, but asking me if I liked reading it is like asking a typical kid if they particularly enjoy eating broccoli.

The Algorithms are laid out rather well, though I did need a professor to walk me through some of them. The algorithms as written didn't quite meet my way of thinking, and so I am giving it 3 stars (-1 for me not enjoying the dry read, and -1 for needing someone to clarify).

[Emil Petersen · Rating 4 out of 5]

Computational geometry is really a neat subject; the problems and the algorithms on how to solve them can almost without exceptions be presented with some figure or drawing. This should definitely not be underestimated and this book uses this fact to a great deal. For the same reason, the algorithms and the problems just does not seem that complicated. You read the text or the pseudocode and think 'what is going on here?', and then you look at the figure illustrating the procedure and suddenly you got it. Amazing. I read the chapters on Convex Hulls, Range search, Point location, Voronoi diagrams, Delaunay triangulation, Motion planning, Visibility graphs, Geometric data structures and Polygon triangulation in great detail. The rest I looked at, but nowhere near the same amount of time. Definitely one of the best books on algorithms I have read.

[Carter · Rating 5 out of 5]

I haven't quite finished reviewing this book. There is a lot of substance here- what happens where you ask, how to bridge the gap between algorithms and geometry? Perhaps, this isn't as general as topology, and there is a fair deal more investigation that needs to take place. Much is unknown about this field. Beautiful book! Recommended.

[Mohamed Ahmed Aboushama · Rating 5 out of 5]

Rainbow picture you need the more experienced in algorithms

[Adrian Vramulet · Rating 4 out of 5]

Didn't read much. Well-explained though.

[Ali Shakiba · Rating 4 out of 5]

This book is fantastic! I am telling this after reading 14 chapters of it. It can take from a month to even 6 8 months to read those 14 chapters. If you just read to get used to the concepts for application purposes, then it should not take much time and effort! But if you want to read it in such a way that you get all the theoretical aspects of it, the time can be extended, for me it took 8 months to read 14 chapters.
There are also a vast variety of exercises included. In the exercises, you might need to read even two to three papers, so you would be able to solve it. The exercises, in my opinion, are based on fresh results or deeper material that were not included in the book to keep it thin!

[Lucy · Rating 3 out of 5]

Read enough for an exam, great book.

[Devendra Owens · Rating 4 out of 5]

The de-facto introduction to Computational Geometry

[Thomas · Rating 5 out of 5]

A very interesting book mixing maths and algorithms. Maybe tougher to read than usual CS books.