**DIMACS - Series in Discrete Mathematics and Theoretical Computer Science**

Volume: 6;
1991;
378 pp;
Hardcover

MSC: Primary 03; 05; 12; 13; 14; 15; 32; 51; 52; 57; 68;

Print ISBN: 978-0-8218-6595-8

Product Code: DIMACS/6

List Price: $84.00

Individual Member Price: $67.20

**Electronic ISBN: 978-1-4704-3964-4
Product Code: DIMACS/6.E**

List Price: $84.00

Individual Member Price: $67.20

# Discrete and Computational Geometry: Papers from the DIMACS Special Year

Share this page *Edited by *
*Jacob Eli Goodman; Richard Pollack; William L. Steiger*

A co-publication of the AMS, DIMACS, and Association for Computing Machinery

The first DIMACS special year, held during 1989–1990, was devoted
to discrete and computational geometry. 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 results of the workshops and the
special year activities. Containing both survey articles and research papers,
this collection presents an excellent overview of 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 stimulation between the two disciplines.

Co-published with the Center for Discrete Mathematics and Theoretical Computer Science beginning with Volume 8. Volumes 1–7 were co-published with the Association for Computer Machinery (ACM).

#### Table of Contents

# Table of Contents

## Discrete and Computational Geometry: Papers from the DIMACS Special Year

- Cover Cover11
- Title page iii4
- Foreword v6
- Preface vii8
- Contents ix10
- Geometric partitioning and its applications 112
- On the convex hull of the integer points in a disc 3950
- Horizon theorems for lines and polygons 4556
- On the perimeter of a point set in the plane 6778
- Lines in space—A collection of results 7788
- Singularities of minimal surfaces and networks and related extremal problems in Minkowski space 95106
- Wu-Ritt characteristic sets and their complexity 111122
- Algorithms in real algebraic geometry and applications to computational geometry 137148
- Ehrhart polynomials of convex polytopes, ℎ-vectors of simplicial complexes, and nonsingular projective toric varieties 165176
- Unimodular fans, linear codes, and toric manifolds 179190
- New results for simplicial spherical polytopes 187198
- Rational-function-valued valuations on polyhedra 199210
- Winding numbers and the generalized lower-bound conjecture 209220
- Computing the center of planar point sets 221232
- Finite quotients of infinite universal polytopes 231242
- The universality theorem on the oriented matroid stratification of the space of real matrices 237248
- The densest double-lattice packing of a convex polygon 245256
- Arrangements in topology 263274
- Notes on geometric graph theory 273284
- Recent progress on the complexity of the decision problem for the reals 287298
- Sweeping arrangements of curves 309320
- On geometric permutations and the Katchalski-Lewis conjecture on partial transversals for translates 351362
- Invariant-theoretic computation in projective geometry 363374
- Back Cover Back Cover1390