Finally: It was stated at the outset, that this system would not be here, and at once,
perfected. You cannot but plainly see that I have kept my word. But I now leave my
cetological system standing thus unfinished, even as the great Cathedral of Cologne was
left, with the crane still standing upon the top of the uncompleted tower. For small
erections may be finished by their first architects; grand ones, true ones, ever leave the
copestone to posterity. God keep me from ever completing anything. This whole book
is but a draft nay, but the draft of a draft. Oh, Time, Strength, Cash, and Patience!
Moby Dick, Herman Melville.
This book started as a collection of class notes on geometric approximation algorithms
that was expanded to cover some additional topics. As the book title suggests, the target
audience of this book is people interested in geometric approximation algorithms.
What is covered. The book describes some key techniques in geometric approxi-
mation algorithms. In addition, more traditional computational geometry techniques are
described in detail (sampling, linear programming, etc.) as they are widely used in devel-
oping geometric approximation algorithms. The chapters are relatively independent and
try to provide a concise introduction to their respective topics. In particular, certain topics
are covered only to the extent needed to present specific results that are of interest. I also
tried to provide detailed bibliographical notes at the end of each chapter.
Generally speaking, I tried to cover all the topics that I believe a person working on
geometric approximation algorithms should at least know about. Naturally, the selection
reflects my own personal taste and the topics I care about. While I tried to cover many
of the basic techniques, the field of geometric approximation algorithms is too large (and
grows too quickly) to be covered by a single book. For an exact list of the topics covered,
see the table of contents.
Naturally, the field of geometric approximation algorithms is a subfield of both com-
putational geometry and approximation algorithms. A more general treatment of ap-
proximation algorithms is provided by Williamson and Shmoys [WS11] and Vazirani
[Vaz01]. As for computational geometry, a good introduction is provided by de Berg et al.
What to cover? The material in this book is too much to cover in one semester. I
have tried to explicitly point out in the text the parts that are more advanced and that can
be skipped. In particular, the first 12 chapters of this book (skipping Chapter 7) provide (I
hope) a reasonable introduction to modern techniques in computational geometry.
Intellectual merit. I have tried to do several things that I consider to be different than
other texts on computational geometry:
(A) Unified several data-structures to use compressed quadtrees as the basic building block
and in the process provided a detailed description of compressed quadtrees.
Previous Page Next Page