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 routing on geometric networks, geometric data structures, mesh generation/manipulation, graph drawing, visualization and pattern recognition. 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 a few examples 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. Currently, I am applying my expertise in geometry to develop algorithms that take advantage of this geometric component resulting in more efficient and reliable communication between wireless devices. The 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. The standard method for modelling wireless networks is through the use of 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. 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?Facility Location is an area where the main focus consists of placing one or more facilities in a region in a manner that optimizes certain criteria with respect to a set of clients. For example, in trying to decide where to build a new fire station in a city, one may want to place it somewhere that minimizes the response time to the target population. Facility Location problems are inherently geometric. Currently, I am studying several variants of this problem and trying to develop efficient solutions.A fundamental question in the manufacturing industry concerning every type of manufacturing process (such as NC-machining or casting) is: Given an object, can it be built using a particular process? I have successfully developed and applied computational geometry techniques to answer some basic problems of this type. Often it is geometric constraints that determine if an object can be built by a particular process. By modelling a process geometrically, we can determine if an object can be constructed at the design stage by determing if a CAD model of an object can be built by a particular manufacturing process. I plan to continue developing algorithms for answering these questions from a geometric perspective.