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.
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 of F-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