Grant: Discovery Grants Program - Individual

My field of research is computational geometry, a field of computer science which focuses on problems with a strong geometric component. The general goal in computational geometry is to take advantage of the geometry of a problem to design faster ---and ultimately optimal--- algorithmic solutions. My long term research objectives involve two general classes of problems that are closely related. 1) Find an optimal way to move in a geometric environment. 2) Find an optimal positioning for an object (a facility) in a geometric environment. I study all these problems from a theoretical perspective, where I consider two general types of geometric environments: discrete and continuous. The solutions to these problems have numerous applications in science and technology, and beyond. In general, I want to understand the trade-offs between extra constraints and extra information in the design of optimal algorithms. To illustrate the first class of problems, suppose that someone wakes up from a nap in the middle of the woods. There is only one path but this person does not remember which direction they came from. It is approximately 15 km long on each side. What should this person do? In computational geometry, this problem is known as searching on a line. In this problem, the goal is to minimize the total distance one has to walk before finding the exit, in the worst case. The optimal strategy is to walk 1 km in one direction and get back. Then, walk twice the distance in the other direction and get back. And repeat until the exit is found. This power--of--two algorithm is used as a black box for several other algorithms in computer science. We can imagine different variants of the same problem. Another example is where we know the coordinates of our destination, but we do not have a full map of the environment. Imagine that we are in Paris, without a map and without GPS or any technology. We want to get to the Eiffel tower, we can see it, but we do not know how to get there. In computational geometry, these problems are referred to as local routing problems. Many of my short term research objectives are inspired by these problems. The second class of problems I focus on is related to finding an optimal location for an object (a facility) in a given environment. We can think of examples that involve an entire population: what should be the trajectory for a new highway or where should we build a new bridge? Where should we build a new hospital or a new airport? People must have access to the facility as easily as possible, but we do not want to expropriate too many people in order to build the facility. My research work involves k-center problems where one looks for k points in the plane that minimize the distance to other points or to a frontier. I also work on optimal-enclosing problems where one wants to compute the optimal curve that encloses a set of points, with respect to a set of constraints.