## Discrete and Computational Geometry: Papers from the DIMACS Special YearJacob E. Goodman, Richard D. Pollack, William L. Steiger 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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

1 | |

On the Convex Hull of the Integer Points in a Disc | 39 |

Horizon Theorems for Lines and Polygons | 45 |

On the Perimeter of a Point Set in the Plane | 67 |

Lines in SpaceA Collection of Results | 77 |

Singularities of Minimal Surfaces and Networks and Related Extremal | 95 |

WuRitt Characteristic Sets and Their Complexity | 111 |

Algorithms in Real Algebraic Geometry and Applications | 136 |

Winding Numbers and the Generalized LowerBound Conjecture | 209 |

Computing the Center of Planar Point Sets | 221 |

Finite Quotients of Infinite Universal Polytopes | 231 |

The Universality Theorem on the Oriented Matroid Stratification | 237 |

The Densest DoubleLattice Packing of a Convex Polygon | 245 |

Arrangements in Topology | 263 |

Notes on Geometric Graph Theory | 273 |

Recent Progress on the Complexity of the Decision Problem for | 287 |

Ehrhart Polynomials of Convex Polytopes AVectors of Simplicial | 165 |

Unimodular Fans Linear Codes and Toric Manifolds | 179 |

New Results for Simplicial Spherical Polytopes | 187 |

Rationalfunctionvalued Valuations on Polyhedra | 199 |

Sweeping Arrangements of Curves | 309 |

On Geometric Permutations and the KatchalskiLewis Conjecture | 351 |

InvariantTheoretic Computation in Projective Geometry | 363 |

### Other editions - View all

Discrete and Computational Geometry: Papers from the DIMACS Special Year Jacob E. Goodman,William L. Steiger No preview available - 1991 |

### Common terms and phrases

algorithm angle apply arrangement ascending set assume bracket bracket polynomial Cayley algebra cells characteristic set Chazelle coefficients combinatorial complexity Computational Geometry Computer Science conjecture connected components consider construction contains convex hull convex polytopes COROLLARY crescent cutting data structure Davenport-Schinzel sequences defined denote dimension Edelsbrunner edges endpoints equation Euclidean exists facets Figure finite formula function Geom geometric graph given half-length parallelogram hump hyperplanes implies inequalities integer interior intersect the sweep intersection points lattice Lemma line segments linear lower bound Math Mathematics Mathematics Subject Classification maximum number nests inside norm obtained oriented matroid pairs parallelogram plane polygon polyhedra problem Proc prove pseudocircles pseudolines quantifier elimination quantifier elimination method real algebraic real closed field result semi-algebraic set Sharir side sign vectors simplex simplicial space Springer-Verlag strictly convex subset theory toric two-intersecting unimodular fans univariate polynomials upper bound variables vertex visible wedge zero