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

Volume: 4;
1991;
608 pp;
Hardcover

MSC: Primary 05;
Secondary 15; 28; 46; 51; 57; 65; 68; 90

Print ISBN: 978-0-8218-6593-4

Product Code: DIMACS/4

List Price: $152.00

AMS Member Price: $121.60

MAA Member Price: $136.80

**Electronic ISBN: 978-1-4704-3962-0
Product Code: DIMACS/4.E**

List Price: $152.00

AMS Member Price: $121.60

MAA Member Price: $136.80

# Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift

Share this page *Edited by *
*Bernd Sturmfels; Peter Gritzmann*

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

This volume, published jointly with the Association for Computing
Machinery, comprises a collection of research articles celebrating the
occasion of Victor Klee's sixty-fifth birthday in September 1990.
During his long career, Klee has made contributions to a wide variety
of areas, such as discrete and computational geometry, convexity,
combinatorics, graph theory, functional analysis, mathematical
programming and optimization, and theoretical computer science. In
addition, Klee made important contributions to mathematics education,
mathematical methods in economics and the decision sciences,
applications of discrete mathematics in the biological and social
sciences, and the transfer of knowledge from applied mathematics to
industry.

In honor of Klee's achievements, this volume presents more than
forty papers on topics related to Klee's research. While the majority
of the papers are research articles, a number of survey articles are
also included. Mirroring the breadth of Klee's mathematical
contributions, this book shows how different branches of mathematics
interact. It is a fitting tribute to one of the foremost leaders in
discrete mathematics.

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).

#### Reviews & Endorsements

The reader of this excellent collection of papers will have the opportunity to be exposed to every current trend in concrete geometry. Highly recommended.

-- The Bulletin of Mathematics Books and Computer Software

# Table of Contents

## Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift

- Cover Cover11
- Title page iii4
- Foreword v6
- Brief Contents vii8
- Preface ix10
- Photo of Victor Klee x11
- Bibliography of Victor Klee xvii18
- Contents xxxi32
- List of papers xxxv36
- A dual forest algorithm for the assignment problem 142
- Self-duality groups and ranks of self-dualities 1152
- Do projections go to infinity? 5192
- The minimal projective plane polyhedral maps 63104
- Packing Euclidean space with congruent cylinders and with congruent ellipsoids 71112
- Extended Euler-Poincarรฉ relations for cell complexes 81122
- Computing the convex hull in the Euclidean plane in linear expected time 91132
- Measures of ๐น-stars in finitely starlike sets 109150
- On sign-nonsingular matrices and the conversion of the permanent into the determinant 117158
- Recognizing properties of periodic graphs 135176
- On generic global rigidity 147188
- Some regular maps and their polyhedral realizations 157198
- Volumes of a random polytope in a convex set 175216
- Bodies of constant width in Riemannian manifolds and spaces of constant curvature 181222
- Uniquely remotal hulls 193234
- The symmetries of the cut polytope and of some relatives 205246
- Complete descriptions of small multicut polytopes 221262
- A hyperplane incidence problem with applications to counting distances 253294
- Gaps in difference sets, and the graph of nearly equal distances 265306
- Remarks on 5-neighbor packings and coverings with circles 275316
- Symmetric solutions to isoperimetric problems for polytopes 289330
- A global Newton method 301342
- Volume approximation of convex bodies by circumscribed polytopes 309350
- Points sets with small integral distances 319360
- Convex minimizers of variational problems 325366
- Flattening a rooted tree 335376
- The geometric complementarity problem and transcending stationarity in global optimization 341382
- Every tree is graceful (but some are more graceful than others) 355396
- Qualitative analysis of Schur complements 359400
- Centers and invariant points of convex bodies 367408
- The diameter of graphs of convex polytopes and ๐-vector theory 387428
- Multiply perspective simplices, Desmic triads and the Edelstein Theorems 413454
- Submanifolds of the cube 423464
- Finite unions of closed subgroups of the ๐-dimensional torus 433474
- Regular triangulations of convex polytopes 443484
- On the number of antipodal or strictly antipodal pairs of points in finite subsets of โ^{๐} 457498
- Multi-order convexity 471512
- Almost orthogonal lines in ๐ธ^{๐} 489530
- Chiral polytopes 493534
- Exact upper bounds for the number of faces in ๐-dimensional Voronoi diagrams 517558
- Stretchability of pseudolines is NP-hard 531572
- A zonotope associated with graphical degree sequences 555596
- Geometry of spaces of homogeneous polynomials on Banach lattices 571612
- The combinatorics of bivariate splines 587628
- Back Cover Back Cover1650