MSc. Maria Saumell Mendiola, Ph.D.

Computational geometry is a young discipline with applications in computer graphics, robotics, geographic information systems and computer vision, among others. It develops algorithms for problems that have a geometric component. While several fundamental problems are solved, new interesting lines of research keep emerging as a result of the many real-life scenarios that can be modelled using Computational geometry tools. One such emerging topic is imprecision (or uncertainty): In many real-life situations, the location of the objects of interest is subject to error, so classical algorithms assuming exact inputs might not be suitable. To be able to deal with these scenarions and be able to describe in which ways the output is affected by small differences in the input, new algorithms are developed.

Geometric graphs are graphs drawn in the Euclidean plane with vertices represented as points and edges represented as straight-line segments. The study of their combinatorial and geometric properties is an important branch of Combinatorial geometry. A prominent example of geometric graphs is the family of proximity graphs, which aims to describe proximity relations among a set of points in the plane. Important proximity graphs are nearest neighbor graphs and the Delaunay triangulation. Some of their properties are still not fully understood. Other challenging open problems in geometric graph theory deal with non-crossing subgraphs such as matchings, paths or cycles. In some instances, vertices of the graph are colored in two or more colors. Several extremal problems on non-crossing geometric graphs remain open.