Discrete and Computational Geometry Papers from the DIMACS Special Year

The first DIMACS special year, held during 1989-1990, was devoted to discrete and computational geometry. More than 200 scientists, both long- and short-term visitors, came to DIMACS to participate in the special year activities. Among the highlights were six workshops at Rutgers and Princeton Universities that defined the focus for much of the special year. The workshops addressed the following topics: geometric complexity, probabilistic methods in discrete and computational geometry, polytopes and convex sets, arrangements, and algebraic and practical issues in geometric computation. This volume presents some of the results growing out of the workshops and the special year activities. Containing both survey articles and research papers, this collection presents an excellent overview of significant recent progress in discrete and computational geometry. The diversity of these papers demonstrate how geometry continues to provide a vital source of ideas in theoretical computer science and discrete mathematics as well as fertile ground for interaction and simulation between the two disciplines.