xii PREFACE (B) Provided a more elaborate introduction to VC dimension, since I find this topic to be somewhat mysterious. (C) Covered some worthy topics that are not part of traditional computational geometry (for example, locality sensitive hashing and metric space partitions). (D) Embedded numerous color figures into the text to illustrate proofs and ideas. Prerequisites. The text assumes minimal familiarity with some concepts in com- putational geometry including arrangements, Delaunay triangulations, Voronoi diagrams, point-location, etc. A reader unfamiliar with these concepts would probably benefit from skimming or reading the fine material available online on these topics (i.e., Wikipedia) as necessary. Tail inequalities (i.e., Chernoff’s inequality) are described in detail in Chap- ter 27. Some specific prerequisites are discussed in Chapter 28. Cross-references. For the convenience of the reader, text cross-references to theo- rems, lemmas, etc., often have a subscript giving the page location of the theorem, lemma, etc., being referenced. One would look like the following: Theorem 19.3p257. Acknowledgments. I had the benefit of interacting with numerous people during the work on this book. In particular, I would like to thank the students that took the class (based on earlier versions of this book) for their input, which helped in discovering numer- ous typos and errors in the manuscript. Furthermore, the content was greatly affected by numerous insightful discussions with Jeff Erickson and Edgar Ramos. Other people who provided comments and insights, or who answered nagging emails from me, for which I am thankful, include Bernard Chazelle, Chandra Chekuri, John Fischer, Samuel Hornus, Piotr Indyk, Mira Lee, Jirka Matoušek, and Manor Mendel. I would especially like to thank Benjamin Raichel for painstakingly reading the text and pointing out numerous errors and typos and for giving guidance on what needed im- provement. His work has significantly improved the quality of the text. I am sure that there are other people who have contributed to this work, whom I have forgotten to mention they have my thanks and apologies. A significant portion of the work on this book was done during my sabbatical (taken during 2006/2007). I thank the people that hosted me during the sabbatical for their hospi- tality and help. Specifically, I would like to thank Lars Arge (Aarhus, Denmark), Sandeep Sen (IIT, New Delhi, India), and Otfried Cheong (KAIST, Daejeon, South Korea). Work on this book was also partially supported by NSF (CAREER) award CCR- 0132901, and AF award CCF-0915984. Errors. There are without doubt errors and mistakes in the text and I would like to know about them. Please email me about any of them that you find. Sariel Har-Peled sariel@uiuc.edu Urbana, IL April 2011
Previous Page Next Page