Geometry is everywhere. An average person will unknowingly generate geometric data in various applications, for instance while using location services or even conducting a financial transaction. Processing such geometric data quickly is integral to providing a fast response. For example, a navigation system requires an efficient algorithm to provide an optimal route. Similarly, taxi companies require a fast algorithm to match cars to customers in order to minimize wait time and travel distance. Despite decades of effort, however, existing algorithms for many such geometric optimization problems are either slow or produce low-quality solutions. In this project, the PI will introduce new techniques and provide a roadmap to design efficient algorithms for select fundamental geometric problems. Given their wide applicability, the PI and his students will not only design algorithms for these problems but also implement, test, optimize and make the code public for the benefit of researchers.
This project will study a number of fundamental optimization problems in computational geometry. These include computation of the Geometric Transportation problem, Geometric Bottleneck Matching, Capacitated Server Allocation, Minimum Weight Triangulation and the Minimum Weight Steiner Triangulation problems. State-of-the-art geometric optimization techniques have severe limitations with respect to these problems. This project will explore three new techniques to make progress on solving these fundamental problems. First, the PI will introduce a new graph-partitioning technique to assist in the design of fast algorithms for matching and transportation problems in geometric and metric settings. Second, the PI will generalize the Hungarian Algorithm to other server-allocation problems and propose to design fast exact, approximation and online algorithms in geometric and metric settings. Third, the PI will explore a probabilistic approach to design polynomial-time approximation schemes for the well-known minimum-weight triangulation and Steiner triangulation problems. This project will also introduce and integrate several novel techniques from various areas including computational geometry and optimization that will assist in bridging the gap between the upper and lower bounds for these problems.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
