Grant: Discovery Grants Program - Individual

My research area is Computational Geometry, a field devoted to the design and analysis of algorithms and data structures for geometric problems. My research focuses both on theoretical and practical issues. The geometric application areas I concentrate on include online routing and path planning in networks, building geometric spanners with various properties, drawing and visualizing graphs, and optimizing various geometric structures. An algorithm that is proven to be theoretically efficient often fails to be practically useful as it may only become efficient when the size of the problem is unreasonably large or the algorithm may be too complex to implement. However, the existence of theoretically efficient algorithms often provides insights into a problem and leads to the development of algorithms that are equally efficient in practice. The main goal of my research has been and continues to be to bridge the gap between theoretical and practical efficiency by finding practical algorithmic solutions to applied geometric problems that have theoretical performance guarantees. Below, I provide an example of the type of geometric problems I am currently concentrating on. More detailed and complete descriptions are provided in the proposal. Communication networks often have an inherent geometric component since the communication devices have physical locations. These networks are often modeled by geometric graphs. A geometric graph is a graph where each vertex is a point in the plane (or possibly higher dimensions depending on the application) and an edge is a line segment or a curve joining two points. The edges are often weighted to represent the distance between two points (or the communication cost etc.). A fundamental problem in this area is to find a path (usually as short as possible) between two points in the graph. Currently, I am applying my expertise in geometry to develop algorithms that take advantage of the geometric component of these graphs to find short paths in an efficient manner. The problems in this area are particularly challenging since the network is often dynamic, i.e. the devices may be moving and edges may appear or disappear. Moreover, this dynamic nature means that no single entity has complete knowledge of the current state of the whole network, requiring the development of algorithms that are online, local and use little memory. This amounts to trying to find a path in a graph while the graph is changing. My research in this area focuses on the following themes: (1) How to route (i.e. find a path) efficiently in a geometric network in various settings, (2) how to construct geometric networks with certain desirable properties? A unifying theme in my research when solving a geometric problem has been to first uncover various geometric properties of the structures involved in the problem, then to attempt to exploit these properties to design efficient data structures and algorithms to solve the geometric problem.