Twentieth Anniversary Volume Discrete & Computational Geometry [Paperback]

This commemorative book contains the 28 major articles that appeared in the 2008 Twentieth Anniversary Issue of the journal Discrete & Computational Geometry, and presents a comprehensive picture of the current state of the field.

The articles in this volume, a number of which solve long-outstanding problems in the field, were chosen by the editors of DCG for the importance of their results, for the breadth of their scope, and to show the intimate connections that have arisen between discrete and computational geometry and other areas of both computer science and mathematics. Apart from the articles, the editors present an expanded preface, along with a set of photographs of groups and individuals who have played a major role in the history of the field during the past twenty years.

This heavily-illustrated book contains twenty-eight major articles that present a comprehensive picture of the current state of discrete and computational geometry. Many of the articles solve long-outstanding problems in the field.

While we were busy putting together the present collection of articles celebrating the twentieth birthday of our journal, Discrete & Computational Geometry, and, in a way, of the ?eld that has become known under the same name, two more years have elapsed. There is no doubt that DCG has crossed the line between childhood and adulthood. By the mid-1980s it became evident that the solution of many algorithmic qu- tions in the then newly emerging ?eld of computational geometry required classical methodsandresultsfromdiscreteandcombinatorialgeometry. Forinstance,visibility and ray shooting problems arising in computer graphics often reduce to Helly-type questions for line transversals; the complexity (hardness) of a variety of geometric algorithms depends on McMullens upper bound theorem on convex polytopes or on the maximum number of halving lines determined by 2n points in tl“Z