Polyhedral Approximation and Other Computational Aspects of Geometric Problems

University Of Denver, Denver CO

Investigators

Abstract

The investigator and his colleague study computational aspects of various geometric problems in two directions: (1) Design and implementation of efficient algorithms for the approximation of various convex and nonconvex objects in multidimensional space by polytopes, and research of the computational complexity as well as practical efficiency of these algorithms. (2) Application of high performance computing as a tool to solve or advance toward a solution of open theoretical problems in convex geometry, among them, Kneser's problem concerning the relationship between volumes of intersections or unions of balls in multidimensional Euclidean space and their mutual distances. Because of its practical importance in many application areas, the approximation of both convex and nonconvex polytopes by "simpler" polytopes is given special attention, and fully constructive solutions are developed for these cases. Extensions and variants such as approximation under various metrics, requiring the approximating object to enclose or be contained within the approximated object, and finding minimal enclosing polytopes of a specific type (like parallelotopes, for example), are also considered. Some of these variants find important applications in mobile computing and multidimensional databases. The investigators develop efficient computational solutions for the problem of approximating multidimensional bodies by polytopes (solids formed by flat faces) of a prescribed size. Such approximation is an important tool in many disciplines, including molecular modeling, optimal control, computer-aided design, and computer visualization. They also investigate the problem of enclosing and approximating multidimensional bodies by polytopes of a prescribed type, such as "boxes" (parallelotopes), for example. Solutions to these problems find important applications in the rapidly growing areas of mobile computing and multidimensional databases. Furthermore, due to their simplicity, polytopes are by far the most widely used form of model representation. Thus, the work is also important because it facilitates the use of the large body of methods already available for polytopes, provided that the resulting approximation is good and can be performed efficiently. Development of these algorithms produces tools of high performance computing. The investigators use these tools in turn to study long-standing geometric problems.