Grant: Discovery Grants Program - Individual

The general theme in this project is the design and analysis of optimization algorithms for geometric problems. The research will concentrate on the following topics: Geometric Spanner Networks and Routing: How to construct a sparse network that connects a given set of sites such that for any two sites, their shortest-path distance in the network is approximately equal to their straight-line distance. Given such a network, how to use geometric information to compute (exact or approximate) shortest paths between any two given sites, how to compute such a path incrementally using only local information. Geometric Data Structures: How to organize geometric data, such that an informative "summary" of the subset of the data that is contained in a query region can be computed. How to organize geometric data in which each data element belongs to some category, such that the different categories inside a query region can be computed. Approximation Algorithms and Fine-Grained Complexity: Given an NP-hard geometric optimization problem, how to design an efficient algorithm that computes a solution that is close to the optimal solution. How to prove conditional lower bounds (based on, for example, the Strong Exponential Time Hypothesis) for geometric optimization problems that can be solved in polynomial time.