9530366 This award supports the research of Professor Klee in combinatorics. During the proposed research period, the emphasis will be in an area that has in recent years been called "Computational Convexity". It forms an interface that involves aspects of convex geometry, discrete mathematics, computer science, and operations research. In essence, it is the study of the computational and algorithmic aspects of high-dimensional convex bodies, especially polytopes. This research is in the general area of Combinatorics. Combinatorics attempts to find efficient methods to study how discrete collections of objects can be arranged. The behavior of discrete systems is extremely important to modern communications. For example, the design of large networks, such as those occurring in telephone systems, and the design of algorithms in computer science deal with discrete sets of objects, and this makes use of combinatorial research. In addition, the type of enumerative information being sought in this project has been of use in the design of geometric algorithms for problems in robotics and motion planning.
