Discrete and Computational Geometry: Papers from the DIMACS Special YearJacob E. Goodman, Richard D. Pollack, William L. Steiger American Mathematical Soc., 1 janv. 1991 - 378 pages 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 des matières
| 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 hVectors 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 | 361 |
Autres éditions - Tout afficher
Discrete and Computational Geometry: Papers from the DIMACS Special Year Jacob E. Goodman,William L. Steiger Aucun aperçu disponible - 1991 |
Expressions et termes fréquents
a₁ algorithm angle apply arrangement ascending set assume B₁ bracket bracket algebra 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 Davenport-Schinzel sequences defined denote dimension Edelsbrunner edges endpoints equation Erdős Euclidean exponential f₁ facets Figure finite formula function g₁ Geom geometric graph given h₁ half-length parallelogram hump hyperplanes integer intersection points k-gon k-intersection k[x₁ lattice Lemma line segments linear lower bound Math Mathematics Mathematics Subject Classification maximum number obtained oriented matroid pairs partition plane polygon polyhedra problem Proc proof 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 subset theorem theory toric varieties triangle unimodular fans univariate polynomials upper bound variables vertex vertices visible x₁ zero