Preface
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 easiest 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. v
- 1
- 2
- 3
前往页