Discrete Mathematics and Theoretical Computer Science

TITLE: "DISCRETE AND COMPUTATIONAL GEOMETRY: Papers from the DIMACS Special Year"

EDITORS: Jacob E. Goodman, Richard Pollack and William Steiger

Published by the American Mathematical Society

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the
AMS Bookstore and
order directly from there.
DIMACS ** does not** distribute or sell these books.

The Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) was established by the National Science Foundation early in 1989. During 1989-1990 more than 200 scientists visited DIMACS to participate in the Special Year in Discrete and Computational Geometry, the first DIMACS "special year." This activity brought together both long-term and short-term visitors whose interests represent the many different communities that contribute to the field. The present volume is a reflection of some of the work that took place during the year.

The year was highlighted by six workshops that defined the focus for much of activity of the Special Year. The topics were: Geometric Complexity (October 16-20, 1989), Probabilistic Methods in Discrete and Computational Geometry (November 27-December 1, 1989), Polytopes and Convex Sets (January 8-12, 1990), Arrangements and Their REalizations (March 19-23, 1990), Practical Issues in Geometric Computation (April 16-20, 1990), and Algebraic Issues in Geometric Computation (May 21-25, 1990).

The volume at hand consists of a number of refereed papers invited from participants in the Special Year. Some were presented at the workshops, including several survey talks, while others were written after their authors' DIMACS visits. All relate in one way or another to the main geometric themes that occupied the attention of the participants during the year. The diversity of the twenty-three papers appearing in this volume attests to the fact that geometry continues to be both a vital source of ideas in theoretical computer science and discrete mathematics as well as a fertile arena in which the two disciplines stimulate each other.

Geometric Partitioning and its Applications Pankaj K. Agarwal 1 On the Convex Hull of the Integer Points in a Disc Antal Balog and Imre Barany 39 Horizon Theorems for Lines and Polygons Marshall Bern, David Eppstein, Paul Plassmann, and Frances Yao 45 On the Perimeter of a Point Set in the Plane Vasilis Capolyeas and Janos Pach 67 Lines in Space-A Collection of Results Herbert Edelsbrunner 77 Singularities of Minimal Surfaces and Networks and Related Extremal Problems in Minkowski Space Z. Furedi, J.C. Lagarias, and F. Morgan 95 Wu-Ritt Characteristic Sets and Their Complexity G. Gallo and B. Mishra 111 Algorithms in Real Algebraic Geometry and Applications to Computational Geometry Joos Heintz, Tomas Recio, and Marie-Francoise Roy 137 Ehrhart Polynomials of Convex Polytopes, h-Vectors of Simplicial Complexes, and Nonsingular Projective Toric Varieties Takayuki Hibi 165 Unimodular Fans, Linear Codes, and Toric Manifolds Peter Kleinschmidt, Niels Schwartz, and Bernd Sturmfels 179 New Results for Simplicial Spherical Polytopes Peter Kleinschmidt and Zeev Smilansky 187 Rational-function-valued Valuations on Polyhedra Jim Lawrence 199 Winding Numbers and the Generalized Lower-Bound Conjecture Carl W. Lee 209 Computing the Center of Planar Point Sets Jiri Matousek 221 Finite Quotients of Infinite Universal Polytopes Peter McMullen and Egon Schulte 231 The Universality Theorem on the Oriented Matroid Stratification of the Space of Real Matrices Nikolai Mnev 237 The Densest Double-Lattice Packing of a Convex Polygon David M. Mount 245 Arrangements in Topology Peter Orlik 263 Notes on Geometric Graph Theory Janos Pach 273 Recent Progress on the Complexity of the Decision Problem for the Reals James Renegar 287 Sweeping Arrangements of Curves Jack Snoeyink and John Hershberger 309 On Geometric Permutations and the Katchalski-Lewis Conjecture on Partial Transversals for Translates Helge Tverberg 351 Invariant-Theoretic Computation in Projective Geometry Neil L. White 363

Index of Volumes

DIMACS Homepage

Contacting the Center

Document last modified on October 28, 1998.