People Making a Difference
Posted January 2009.
Klee contributed to combinatorics, convexity, algorithms, and optimization problems but his work always had a strongly geometric flavor....
Mathematics has a reputation as a subject of austere beauty - a subject that resonates for some people the way that a beautiful sunrise or sunset, a beautiful symphony, or a beautiful painting might for other people. Yet mathematics also has its applied side. Without mathematics that was developed in the 20th century we would not have the cell phones that are radically changing the way we live our lives in the early 21st century. Against a backdrop of the dual aspects of mathematics, its beauty and applicability, is the sense that the frontiers of mathematics are getting further and further from what an "average person," one not pursuing a career in mathematics or one of its closely allied fields, can master. There has been an increase in the length and complexity of mathematical proofs and in some cases, important theorems have required a computer in an integral way. Examples of this are the results of Wolfgang Haken and Kenneth Appel that confirm the conjecture that every plane map can have its faces colored with 4 or fewer colors and Thomas Hale confirming the maximal density that spheres packed in 3-space can achieve.
His recent death (August 2007) is a great loss for the mathematics community. His published works included several books and over 240 research papers. Klee was born in San Francisco in 1925 and attended Pomona College with a major in both mathematics and chemistry. Whereas prior to the 20th century nearly all mathematicians (e.g. Newton, Gauss, Euler, Laplace, etc.) made contributions to not only mathematics but physics or some other branch of science, the pressures of specialization have made this more rare. Although most of Klee's work had a geometric focus, his work spanned a wide range of interests motivated by both theoretical and applied considerations. He received his doctorate degree from the University of Virginia, where he studied with the prominent topologist Edward McShane. His doctoral thesis (1949) was entitled:
Figure 1: Geometric sets can look different but be topologically equivalent.
What is geometry?
During the early part of the 20th century the study of geometry was at a crossroads. During the late 19th century the world of geometry was rocked by what turned out to be one of the great milestones of intellectual history, not only from the point of view of mathematics but knowledge in general.
Figure 2: A model for a geometry with many lines parallel to a given line through a point.
(Harold Scott MacDonald Coxeter, known as Donald Coxeter)
Klee's mathematics ranged across many aspects of geometry. In what follows I would like to call attention to three important results that Klee was involved with, which can be discussed in elementary terms: Art Gallery theorems, the Klee-Minty polytopes, and Kleetopes. First, I will sample a few items which show his blend of interests in topics that touch both theoretical and applicable mathematics. He made especially important contributions to the theory of convex polytopes, notably, polytopes in higher dimensional spaces. A polytope is a bounded convex set which is the intersection of the higher dimensional analogue of planes. (Note: A set is convex when for any two points p and q in the set, the line segment joining p and q is also in the set.)
Figure 3: Interior of a convex pentagon (left); non-convex pentagon (right)
During World War II large numbers of men and vast amounts of material had to be transferred from the United States to the European and Pacific war theaters. The United States, in the throes of coming out of the Great Depression, had refitted its factories to manufacture the material of war rather than consumer products. A new sub-discipline within mathematics, variously called operations research or management science, was to emerge in the aftermath of the war. The roots of this work were laid down by the need to find mathematical tools for fighting the war successfully. (Another triumph of mathematics during the war was in breaking both German and Japanese codes.) After the War, being able to solve large problems in production management, scheduling, cost minimization, etc. became increasingly important for governments, industry, and businesses.
The inequalities above correspond to the interior points of a polygon in 2-dimensional space (shown in red in Figure 4, below. Can you find the coordinate of the point G?). In more general problems there are typically hundreds of variables with perhaps thousands of constraints. These questions lead to problems about the generalization of the polygon concept to higher dimensional spaces. These are the objects known as polytopes. It turns out that the points which satisfy such constraints must be the points on or inside a higher dimensional polytope. However, remarkably, it can be shown that the optimal solution of such a problem always lies at a vertex of the "feasible" polyhedron. In the diagram in Figure 4, there are 4 points to which we can restrict attention in trying to determine where the maximum value occurs among all points that satisfy the constraints. The theorem which gives this result is sometimes known as the Corner Point Theorem. Another way of putting this result is that miraculously, instead of having to check infinitely many points to see where an optimal (best) solution occurs, it is only necessary to check a finite number of points, the corners, to see where the best solution occurs.
Figure 4: (The points which satisfy the contents of a linear programming problem.)
Figure 5 : Diagram of a 4-cube
Early on in the history of polyhedra, the question of whether or not a polyhedron had a simple closed circuit which included all its vertices, a hamiltonian circuit, has been of interest. Part of this interest stemmed from the fact that if a convex polyhedron with at least three edges at a vertex has a hamiltonian circuit then its faces can be colored with 4 colors. The way to see this is that the graph of an convex 3-dimensional polyhedron P can be drawn in the plane. Once one has such a "plane" drawing, if there is a hamiltonian circuit for the graph (consisting of the vertices and edges of P), then by the Jordan Curve Theorem applied to the hamiltonian circuit, there are faces on the inside of the graph and on the outside of the graph. Now one can color the interior faces with 2 colors and the exterior faces with 2 colors. A typical example is shown in the diagram below. Notice that there is a special face in this diagram, colored turquoise, that surrounds all of the other faces of the graph. The hamiltonian circuit is shown with thick black edges. The two colors used for the faces inside the hamiltonian circuit are red and green, while the faces in the exterior of the hamiltonian circuit are colored blue and turquoise.
Figure 6: The regions of a graph drawn in the plane which has a hamiltonian circuit colored with 4 colors.
Figure 7: The graph of a polyhedron with all faces being triangles.
Figure 8: Pyramids drawn on all of the faces of the polyhedron in Figure 7. This new polyhedron is known as a Kleetope.
Of these three remarkable achievements, the role Klee played in the development of "art gallery" theorems is the most recent. In 1973 the young Czech mathematician Vasek Chvatál challenged Victor Klee to describe an "interesting" problem in elementary geometry. Klee responded with the following problem.
Alexandrov, A., Convex Polyhedra, Springer, Heidelberg, 2005.
Those who can access JSTOR can find some of the papers mentioned above there. For those with access, the American Mathematical Society's MathSciNet can be used to get additional bibliographic information and reviews of some these materials. Some of the items above can be accessed via the ACM Portal , which also provides bibliographic services.
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Search Feature Column
Feature Column at a glance