DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME FOUR
TITLE: "APPLIED GEOMETRY AND DISCRETE MATHEMATICS"
EDITORS: Peter Gritzmann and Bernd Sturmfels
Published by the American Mathematical Society


Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

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.



PREFACE


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

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.


TABLE OF CONTENTS




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 Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.