DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME SIX
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

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

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.

PREFACE

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.

TABLE OF CONTENTS



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 Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.