Grants and Contributions:

Grant or Award spanning more than one fiscal year. (2017-2018 to 2022-2023)

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: 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 Graph Augmentation: How to add a small number of links to an existing geometric network, such that the longest distance in the resulting augmented network is minimized. For a given geometric network and given location on it, how to compute the locations in the network that are farthest away.
Optimal Subgraphs of Geometric Graphs: Given a set of red and blue points, how to compute a shortest (or longest) spanning tree in which each link connects a red point with a blue point. How to compute such a tree if no two links are allowed to cross.
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.