Victor Klee (1925–2007): The Architect of Modern Convexity
Victor Klee was a titan of 20th-century mathematics whose work bridged the gap between abstract geometry and the practical world of computer science and optimization. A prolific researcher and a dedicated educator, Klee is best remembered for his profound contributions to the study of convex sets, functional analysis, and the efficiency of algorithms.
1. Biography: From San Francisco to Seattle
Victor LaRue Klee Jr. was born on September 18, 1925, in San Francisco, California. A precocious student, he entered Pomona College at a young age, earning his B.A. in Mathematics and Chemistry in 1945. He then moved to the University of Virginia, where he completed his Ph.D. in 1949 in just a few years under the supervision of Edward J. McShane. His dissertation focused on convex sets in linear spaces, a theme that would define his career.
After a brief stint as an instructor and assistant professor at the University of Virginia, Klee joined the faculty of the University of Washington (UW) in 1953. He remained at UW for the rest of his career, becoming a cornerstone of the department and serving as a Professor of Mathematics and Applied Mathematics. He also held visiting positions at prestigious institutions, including the University of Copenhagen and ETH Zurich. Klee passed away on August 17, 2007, in Lakewood, Ohio, leaving behind a legacy as one of the most versatile mathematicians of his era.
2. Major Contributions: Geometry and Complexity
Klee’s intellectual fingerprint can be found across several mathematical disciplines. His work was characterized by an ability to take intuitive geometric concepts and apply them to rigorous computational problems.
The Klee-Minty Cube and the Simplex Method
Perhaps his most famous contribution (with George Minty) was the creation of the "Klee-Minty cube." In 1972, they demonstrated that the Simplex algorithm—the primary tool for solving linear programming problems—does not run in "polynomial time" in the worst-case scenario. By constructing a slightly deformed hypercube, they showed the algorithm might be forced to visit every single vertex, proving that the method was exponentially complex in theory, even if it remained efficient in practice.
The Art Gallery Problem
In 1973, Klee posed a deceptively simple question:
"How many guards are needed to see every point in the interior of an $n$-walled art gallery?"This sparked a new subfield of computational geometry. (The answer, $\lfloor n/3 \rfloor$, was later proven by Václav Chvátal).
Klee’s Measure Problem
He challenged the mathematical community to find the most efficient way to calculate the area (or volume) of the union of $n$ axis-aligned rectangles. This problem remains a fundamental benchmark in the development of data structures and geometric algorithms.
Convexity and Functional Analysis
Klee was a world authority on the geometry of convex sets. He explored the properties of "exposed points" and "extreme points" in infinite-dimensional spaces, providing insights that are now essential to functional analysis and optimization theory.
3. Notable Publications
Klee was an exceptionally clear writer who published over 250 papers. Some of his most influential works include:
- "How Good is the Simplex Algorithm?" (1972): Co-authored with George Minty, this paper is a landmark in the history of computational complexity.
- "On the number of vertices of a convex polytope" (1964): A foundational paper in the study of polytopes.
- "What is a Convex Set?" (1971): This expository piece won the Chauvenet Prize for its clarity and brilliance in explaining complex concepts to a broader audience.
- "Old and New Unsolved Problems in Plane Geometry and Number Theory" (1991): Co-authored with Stan Wagon, this book is beloved for its engaging presentation of accessible yet difficult mathematical puzzles.
4. Awards & Recognition
Klee’s contributions were recognized by the highest echelons of the mathematical community:
- President of the Mathematical Association of America (MAA): He served from 1971 to 1972.
- The Chauvenet Prize (1972): Awarded for outstanding expository writing.
- MAA Award for Distinguished Service to Mathematics (1977): Recognizing his influence on the teaching and administration of the field.
- Gundelfinger Prize: For his contributions to optimization.
- Honorary Doctorates: He received honorary degrees from several institutions, including Pomona College and the University of Trier.
- Guggenheim Fellow: Awarded in 1959.
5. Impact & Legacy
Victor Klee was a "problem solver" in the truest sense. While some mathematicians focus on building massive, abstract theories, Klee focused on specific, often visual, problems that revealed deep truths about the nature of space and computation.
His work on the Simplex algorithm paved the way for the development of "Interior Point Methods," which are now standard in industrial optimization. In the world of Computer Science, his "Measure Problem" and "Art Gallery Problem" are foundational to the curriculum of computational geometry. Beyond his research, he was a legendary mentor, supervising over 30 Ph.D. students and influencing generations of mathematicians through his presidency of the MAA.
6. Collaborations
Klee was a highly social mathematician who thrived on collaboration.
- George Minty: Their partnership led to the definitive critique of the Simplex method.
- Branko Grünbaum: A colleague at the University of Washington; together, they advanced the theory of convex polytopes and tiling.
- Stan Wagon: With whom he shared a passion for mathematical exposition and unsolved problems.
- Students: His Ph.D. students, such as Robert Phelps (known for the Bishop-Phelps theorem), went on to become major figures in functional analysis.
7. Lesser-Known Facts
- The "Klee-Minty" Name: Because of the fame of the Klee-Minty cube, many younger mathematicians assumed "Klee-Minty" was a single person or a type of dessert. In reality, it represented the union of two very different mathematical minds.
- An Avid Mountaineer: Klee was a devoted hiker and mountain climber. He often remarked that the terrain of the Pacific Northwest served as a physical manifestation of the geometric landscapes he explored in his mind.
- Problem Columnist: For many years, Klee edited the "Problems" section of the American Mathematical Monthly. He believed that a well-posed problem was often more valuable to the progress of science than a completed proof.
- The "Klee" Name in Botany: While Victor was a mathematician, his father, Victor LaRue Klee Sr., was a noted figure in the world of horticulture—a different kind of "growth" entirely.