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 adhoc routing in wireless networks, geometric networks, mesh generation/manipulation, graph drawing, visualization and pattern recognition. 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. Communication between wireless devices has an inherent geometric component since these devices have a physical location which is constantly changing. Problems in this area are particularly challenging since the network is dynamic, i.e. the wireless devices are usually moving. Moreover, this dynamic nature means that no single entity has complete knowledge of the whole network, requiring the development of algorithms that are online and use little memory. My research in this area focuses on the following themes: (1) How to route (i.e. find a path) efficiently in a geometric network, (2) How to construct geometric networks with certain desirable properties?