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.
Table of contents:
Pankaj K Agarwal, Geometric partitioning and its applications; Antal Balog and Imre Barany, On the convex hull of the integer points in a disc; Marshall Bern, David Eppstein, Paul Plassmann, and Frances Yao, Horizon theorems for lines and polygons; Vasilis Capolyeas and Janos Pach, On the perimeter of a point set in the plane; Herbert Edelsbrunner, Lines in a space-a collection of results; Z Furedi, J C Lagarias and F Morgan, Singularities of minimal surfaces and networks and related external problems in Minkowski space; G Gallo and B Mishra, Wu-Ritt characteristic sets and their complexity; Joos Heintz, Tomas Recio and Marie-Francoise Roy, Algorithms in real algebraic geometry and applications to computational geometry; Takayuki Hibi, Ehrhart polynomials of convex polytopes, h-vectors of simplicial complexes, and nonsingular projective toric varieties; Peter Kleinschmidt, Niels Schwartz, and Bernd Sturmfels, Unimodular fans, linear codes, and toric manifolds; Peter Kleinschmidt and Zeev Smilansky, New results for simplical spherical polytopes; Jim Lawrence, Rational-function-valued valuations on polyhedra; Carl W Lee, Winding numbers and the generalized lower-bound conjecture; Jiri Matousek, Computing the center of planar point sets; Peter McMullen and Egon Schulte, Finite quotients of infinite universal polytopes, Nikolai Mnev, The universality theorem on the oriented matroid double-lattice packing of a convex polygon; Peter Orlik, Arrangements in topology; Janos Pach, Notes on geometric graph theory; James Renegar, Recent progress on the complexity of the decision problem for the reals; Jack Snoeyink and John Hershberger, Sweeping arrangements of curves; Helge Tverberg, On geometric permutations and the Katchalski-Lewis conjecture on partial transversals for translates; Neil L White, Invariant-theoretic computation in projective geometry.
Table of contents:
Pankaj K Agarwal, Geometric partitioning and its applications; Antal Balog and Imre Barany, On the convex hull of the integer points in a disc; Marshall Bern, David Eppstein, Paul Plassmann, and Frances Yao, Horizon theorems for lines and polygons; Vasilis Capolyeas and Janos Pach, On the perimeter of a point set in the plane; Herbert Edelsbrunner, Lines in a space-a collection of results; Z Furedi, J C Lagarias and F Morgan, Singularities of minimal surfaces and networks and related external problems in Minkowski space; G Gallo and B Mishra, Wu-Ritt characteristic sets and their complexity; Joos Heintz, Tomas Recio and Marie-Francoise Roy, Algorithms in real algebraic geometry and applications to computational geometry; Takayuki Hibi, Ehrhart polynomials of convex polytopes, h-vectors of simplicial complexes, and nonsingular projective toric varieties; Peter Kleinschmidt, Niels Schwartz, and Bernd Sturmfels, Unimodular fans, linear codes, and toric manifolds; Peter Kleinschmidt and Zeev Smilansky, New results for simplical spherical polytopes; Jim Lawrence, Rational-function-valued valuations on polyhedra; Carl W Lee, Winding numbers and the generalized lower-bound conjecture; Jiri Matousek, Computing the center of planar point sets; Peter McMullen and Egon Schulte, Finite quotients of infinite universal polytopes, Nikolai Mnev, The universality theorem on the oriented matroid double-lattice packing of a convex polygon; Peter Orlik, Arrangements in topology; Janos Pach, Notes on geometric graph theory; James Renegar, Recent progress on the complexity of the decision problem for the reals; Jack Snoeyink and John Hershberger, Sweeping arrangements of curves; Helge Tverberg, On geometric permutations and the Katchalski-Lewis conjecture on partial transversals for translates; Neil L White, Invariant-theoretic computation in projective geometry.