Discrete Mathematics and Theoretical Computer Science

TITLE: "APPLIED GEOMETRY AND DISCRETE MATHEMATICS"

EDITORS: Peter Gritzmann and Bernd Sturmfels

Published by the American Mathematical Society

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.

This volume comprises a collection of research articles dedicated to Victor Klee on the occasion of his 65th birthday in September 1990. All papers are related to Victor Klee's research work, and, in view of his borad interests, a wide range of areas in mathematics and its applications are touched upon here. These areas include

- Discrete and Computational Geometry,
- Classical and Computational Convexity,
- Convex Polytopes and their Relatives,
- Combinatorics, Polyhedral Combinatorics, and Graph Theory,
- Functional Analysis,
- Mathematical Programming and Optimization, and
- Theoretical Computer Science.

Victor Klee has made significant contributions not only to all of the above fields, but also to mathematics education, mathematical methods in economics and the decision sciences, applications of discrete mathematics in the biological and social sciences, and information linkage between applied mathematics and industry. Rather than attempting to summarize or comment on Victor Klee's numerous professional achievements, we let his vita and bibliography speak for themselves.

Following the spirit of victor Klee's Holistic view of mathematics, the present collection is not divided into mathematical subcategories, but the articles appear in alphabetical order by first author. In order to facilitate browsing through this volume and to give easy access to papers belonging to the same area, we include a list of papers by subject area.

We are indebted to the Center for Discrete Mathematics and Theorectical Computer Science, in particular to its director Daniel Gorenstein, and to the American Mathematical Society for their help in arranging the publication of this volume. We wish to thank the referees for their invaluable help and the authors for their enthusiastic support throughout this project. But, above all we join all contributors in their birthday wishes expressing the deepest gratitude to Victor Klee for all that he has given to us.

Preface ix Biography of Victor Klee xi Bibliograph of Victory Klee xvii Contents (in alphabetical order by author) xxxi List of Papers (by subjects) xxxv Contents A Dual Forest Algorithm for the Assignment Problem HANS ACHATZ, PETER KLEINSCHMIDT, AND KONSTANTINOS PAPARRIZOS 1 Self-duality Groups and Ranks of Self-dualities JONATHAN ASHLEY, BRANKO GRUNBAUM, G. C. SHEPHARD, AND WALTER STROMQUIST 11 Do Projections Go to Infinity? IMRE BARANY, JACOB E. GOODMAN, AND RICHARD POLLACK 51 The Minimal Projective Plane Polyhedral Maps D. W. BARNETTE 63 Packing Euclidean Space with Congruent Cylinders and with Congruent Ellipsoids A. BEZDEK AND W. KUPERBERG 71 Extended Euler-Poincare Relations for Cell Complexes ANDERS BJORNER AND GIL KALAI 81 Computing the Convex Hull in the Euclidean Plane in Linear Expected Time KARL HEINZ BORGWARDT, NORBERT GAFFKE, MICHAEL JUNGER, AND GERHARD REINELT 91 Measures ofF-Stars in Finitely Starlike Sets MARILYN BREEN 109 On Sign-Nonsingular Matrices and the Conversion of the Permanent into the Determinant RICHARD A. BRUALDI AND BRYAN L. SHADER 117 Recognizing Properties of Periodic Graphs EDITH COHEN AND NIMROD MEGIDDO 135 On Generic Global Rigidity ROBERT CONNELLY 147 Some Regular Maps and Their Polyhedral Realizations H. S. M. COXETER AND G. C. SHEPHARD 157 Volumes of a Random Polytope in a Convex Set L. DALLA AND D. G. LARMAN 175 Bodies of Constant Width in Riemannian Manifolds and Spaces of Constant Curvature B. V. DEKSTER 181 Uniquely Remotal Hulls DUANE DETEMPLE, JACK ROBERTSON, AND GRAHAM WOOD 193 The Symmetries of the Cut Polytope and of Some Relatives M. DEZA, V. P. GRISHUKHIN, AND M. LAURENT 205 Complete Descriptions of Small Multicut Polytopes M. DEZA, M. GROTSCHEL. AND M. LAURENT 221 A Hyperplane Incidence Problem with Applications to Counting Distances HERBERT EDELSBRUNNER AND MICHA SHARIR 253 Gaps in Difference Sets, and the Graph of Nearly Equal Distances PAUL ERDOS, ENDRE MAKAI. JANOS PACH, AND JOEL SPENCER 265 Remarks on 5-Neighbor Packings and Coverings with Circles G. FEJES TOTH AND L. FEJES TOTH 275 Symmetric Solutions to Isoperimetric Problems for Polytopes P. FILLIMAN 289 A Global Newton Method A. A. GOLDSTEIN 301 Volume Approximation of Convex Bodies by Circumscribed Polytopes PETER M. GRUBER 309 Points Sets with Small Integral Distances HEIKO HARBORTH AND LOTHAR PIEPMEYER 319 Convex Minimizers of Variational Problems ERHARD HEIL 325 Flattening a Rooted Tree PAUL HILFINGER, EUGENE L. LAWLER, AND GUNTER ROTE 335 The Geometric Complementarity Problem and Transcending Stationarity in Global Optimization REINER HORST AND HOANG TUY 341 Every Tree is Graceful (But Some are More Graceful than Others) T. C. HU AND A. B. KAHNG 355 Qualitative Analysis of Schur Complements CHARLES R. JOHNSON AND JOHN MAYBEE 359 Centers and Invariant Points of Convex Bodies M. J. KAISER, T. L. MORIN, AND T. B. TRAFALIS 367 The Diameter of Graphs of Convex Polytopes and f-Vector Theory GIL KALAI 387 Multiply Perspective Simplices, Desmic Triads and the Edelstein Theorems L. M. KELLY 413 Submanifolds of the Cube W. KUHNEL AND CH. SCHULZ 423 Finite Unions of Closed Subgroups of the n-Dimensional Torus JIM LAWRENCE 433 Regular Triangulations of Convex Polvtopes CARL W. LEE 443 On the Number of Antipodal or Strictly Antipodal Pairs of Points in Finite Subsets Of Rd E. MAKAI, JR. AND H. MARTINI 457 Multi-Order Convexity JUAN-ENRIQUE MARTINEZ-LEGAZ AND IVAN SINGER 471 Almost Orthogonal Lines in Ed MOSHE ROSENFELD 489 Chiral Polytopes EGON SCHULTE AND ASIA IVIC WEISS 493 Exact Upper Bounds for the Number of Faces in d-Dimensional Voronoi Diagrams RAIMUND SEIDEL 517 Stretchabilltv of Pseudolines is NP-Hard PETER W. SHOR 531 A Zonotope Associated with Graphical Degree Sequences RICHARD P. STANLEY 555 Geometry of Spaces of Homogeneous Polynomials on Banach Lattices K. SUNDARESAN 571 The Combinatorics of Bivariate Splines WALTER WHITELEY 587

Index of Volumes

DIMACS Homepage

Contacting the Center

Document last modified on October 28, 1998.