The purpose of this project is to use algorithms from computational geometry to solve problems in mathematical optimization and to apply concepts from optimization to solve problems in computational geometry. Although the fields of geometry and optimization have enjoyed a long history of cross-pollination, this project will specifically focus on infinite-dimensional optimization, which has not historically benefited from geometric analysis. The research problems that are the focus of this study can be applied to a variety of problems across many domains, such as geospatial analysis, transportation theory, ecological conservation, mechanism design, and political science. This project includes an extensive outreach program that leverages existing relationships with industry, government, and underrepresented groups as a basis for hands-on activities with students at the high school, undergraduate, and graduate levels. By involving these collaborators, this project will allow students to understand the concerns of practitioners in addition to those of academics, thus ensuring that our work will have both an intellectual and social benefit.
The key theme of this research is the use of knowledge in one field, namely computational geometry or infinite-dimensional optimization, to solve a problem in the other. For example, an infinite-dimensional optimization problem might have an infinite-dimensional variable space, an infinite-dimensional constraint space, or both. When one of these spaces has an appropriate geometric structure associated with it, we have shown that it is sometimes possible to reduce an infinite-dimensional set to one that is finite; one might use convexity or monotonicity properties of the Euclidean distance function to identify a finite set of "bottleneck points" that are sufficient for feasibility of the entire problem, thereby reducing its complexity. As a second example, many problems in computational geometry are concerned with the construction of "equitable" shapes, meaning shapes that have (for example) equal area, mass, perimeter, or volume. We have identified problem attributes in which certain "equity" constraints are actually equivalent to the optimality conditions of a convex optimization problem, which again reduces the complexity of the original problem. The problems and methods introduced in this research are therefore representative of a new set of tools that complement the arsenal of modern operations researchers and computational geometers, synthesizing elements from both fields.
