Victor L. Klee
|Died||August 17, 2007 81) (aged|
Lakewood, Ohio, U.S.
|Alma mater||University of Virginia (Ph.D.)|
|Institutions||University of Washington|
|Thesis||Convex Sets in Linear Spaces (1949)|
|Doctoral advisor||Edward James McShane|
Victor L. Klee, Jr. (September 18, 1925 – August 17, 2007) was a mathematician specialising in convex sets, functional analysis, analysis of algorithms, optimization, and combinatorics. He spent almost his entire career at the University of Washington in Seattle.
Born in San Francisco, Vic Klee earned his B.A. degree in 1945 with high honors from Pomona College, majoring in mathematics and chemistry. He did his graduate studies, including a thesis on Convex Sets in Linear Spaces, and received his PhD in mathematics from the University of Virginia in 1949. After teaching for several years at the University of Virginia, he moved in 1953 to the University of Washington in Seattle, Washington, where he was a faculty member for 54 years.He died in Lakewood, Ohio.
Klee wrote more than 240 research papers. He proposed Klee's measure problem and the art gallery problem. Kleetopes are also named after him, as is the Klee–Minty cube, which shows that the simplex algorithm for linear programming does not work in polynomial time in the worst–case scenario.
Klee served as president of the Mathematical Association of America from 1971 to 1973.In 1972 he won a Lester R. Ford Award.
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset.
Linear programming is a method to achieve the best outcome in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming.
In mathematical optimization, Dantzig's simplex algorithm is a popular algorithm for linear programming.
Hugo Hadwiger was a Swiss mathematician, known for his work in geometry, combinatorics, and cryptography.
In geometry, Radon's theorem on convex sets, published by Johann Radon in 1921, states that any set of d + 2 points in Rd can be partitioned into two sets whose convex hulls intersect. A point in the intersection of these convex hulls is called a Radon point of the set.
Branko Grünbaum was a Yugoslavian-born mathematician of Jewish descent and a professor emeritus at the University of Washington in Seattle. He received his Ph.D. in 1957 from Hebrew University of Jerusalem in Israel.
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the -dimensional Euclidean space . Most texts use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue. Yet other texts identify a convex polytope with its boundary.
In computational geometry, Klee's measure problem is the problem of determining how efficiently the measure of a union of (multidimensional) rectangular ranges can be computed. Here, a d-dimensional rectangular range is defined to be a Cartesian product of d intervals of real numbers, which is a subset of Rd.
In mathematics, convex geometry is the branch of geometry studying convex sets, mainly in Euclidean space. Convex sets occur naturally in many areas: computational geometry, convex analysis, discrete geometry, functional analysis, geometry of numbers, integral geometry, linear programming, probability theory, game theory, etc.
In mathematics, the vertex enumeration problem for a polytope, a polyhedral cell complex, a hyperplane arrangement, or some other object of discrete geometry, is the problem of determination of the object's vertices given some formal representation of the object. A classical example is the problem of enumeration of the vertices of a convex polytope specified by a set of linear inequalities:
Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.
Alan Jerome Hoffman was an American mathematician and IBM Fellow emeritus, T. J. Watson Research Center, IBM, in Yorktown Heights, New York. He was the founding editor of the journal Linear Algebra and its Applications, and held several patents. He contributed to combinatorial optimization and the eigenvalue theory of graphs. Hoffman and Robert Singleton constructed the Hoffman–Singleton graph, which is the unique Moore graph of degree 7 and diameter 2.
Raimund G. Seidel is a German and Austrian theoretical computer scientist and an expert in computational geometry.
In geometry and polyhedral combinatorics, an integral polytope is a convex polytope whose vertices all have integer Cartesian coordinates. That is, it is a polytope that equals the convex hull of its integer points. Integral polytopes may also be called convex lattice polytopes or Z-polytopes. The special cases of two- and three-dimensional integral polytopes may be called polygons or polyhedra instead of polytopes, respectively.
In geometry and polyhedral combinatorics, a k-neighborly polytope is a convex polytope in which every set of k or fewer vertices forms a face. For instance, a 2-neighborly polytope is a polytope in which every pair of vertices is connected by an edge, forming a complete graph. 2-neighborly polytopes with more than four vertices may exist only in spaces of four or more dimensions, and in general a k-neighborly polytope requires a dimension of 2k or more. A d-simplex is d-neighborly. A polytope is said to be neighborly, without specifying k, if it is k-neighborly for . If we exclude simplices, this is the maximum possible k: in fact, every polytope that is k-neighborly for some is a simplex.
In mathematical optimization, the criss-cross algorithm is any of a family of algorithms for linear programming. Variants of the criss-cross algorithm also solve more general problems with linear inequality constraints and nonlinear objective functions; there are criss-cross algorithms for linear-fractional programming problems, quadratic-programming problems, and linear complementarity problems.
The Klee–Minty cube or Klee–Minty polytope is a unit hypercube of variable dimension whose corners have been perturbed. Klee and Minty demonstrated that George Dantzig's simplex algorithm has poor worst-case performance when initialized at one corner of their "squashed cube". On the three-dimensional version, the simplex algorithm and the criss-cross algorithm visit all 8 corners in the worst case.
Combinatorial Geometry in the Plane is a book in discrete geometry. It was translated from a German-language book, Kombinatorische Geometrie in der Ebene, which its authors Hugo Hadwiger and Hans Debrunner published through the University of Geneva in 1960, expanding a 1955 survey paper that Hadwiger had published in L'Enseignement mathématique. Victor Klee translated it into English, and added a chapter of new material. It was published in 1964 by Holt, Rinehart and Winston, and republished in 1966 by Dover Publications. A Russian-language edition, Комбинаторная геометрия плоскости, translated by I. M. Jaglom and including a summary of the new material by Klee, was published by Nauka in 1965. The Basic Library List Committee of the Mathematical Association of America has recommended its inclusion in undergraduate mathematics libraries.
Convex Polytopes is a graduate-level mathematics textbook about convex polytopes, higher-dimensional generalizations of three-dimensional convex polyhedra. It was written by Branko Grünbaum, with contributions from Victor Klee, Micha Perles, and G. C. Shephard, and published in 1967 by John Wiley & Sons. It went out of print in 1970. A second edition, prepared with the assistance of Volker Kaibel, Victor Klee, and Günter M. Ziegler, was published by Springer-Verlag in 2003, as volume 221 of their book series Graduate Texts in Mathematics.