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
Previous Page Next Page