I work in computational geometry, a field in between discrete mathematics and computer science. I focus in the design of efficient algorithms (that are often based on some geometric properties of the problem). Although my work is of theoretical nature, I try to work on problems that have a high potential for application.

In the following I list a selection of the latest research topics I have been working on.

Geometric shortest path planning

Path planning problems are simply described as the search for the best way to reach the desired destination from the starting point. Although the basic "find the fastest/cheapest route to reach some target destination" problem is relatively easy (many devices such as GPS navigation systems solve these type of problems in our daily lives), the topic is very diverse and still has many challenging open problems. For example, how to find the route when the environment is not fully known (as it happens in sensor networks), consider possible shortcuts (that is, places where one travels fast), and a large et cetera.

Within this topic I have worked in both descriptive and augmenting problems. Descriptive problems are those in which you want some kind of information (for example, what is the worst-case response time that an emergency service could take?) whereas augmenting problems aim at enhancing the environment (where should I build a new highway so that overall transportation within the city is improved?).

Memory constrained algorithms

Another type of problems I have been working on is the design of algorithms that use as few memory as possible. The processing power of nowadays computers does not grow as fast as our capabilities of gathering information. Thus, it becomes desirable to have algorithms that can extract information from large datasets (such as the internet, or the one extracted from a social network) that do not fit explicitly into memory. In addition to working for some geometric problems within the family, I have created some general tools that can be used for a large family of problems. As a member of Kawarabayashi?s ERATO large graph project (more information in Future Goals section below) we are now working in a practical implementation of these algorithms as a way to reduce the memory of each node within a large network.

Battery management in ad-hoc networks

I also studied some battery management algorithms in ad-hoc networks. Such networks are often created by a large number of small sensors that coordinate to solve some task (like monitoring a region). We would like these devices to be autonomous and that can ideally work without a big power source. I have designed algorithms that help dealing with this problem in two ways: network creation (determine how should sensors should communicate so that not much energy is spent in transmission) and message transmission (establishing communication protocols to certify that the message will reach its destination).