Preface

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.

[dBCvKO08].

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.

xi