Researchers who, allegedly, “cannot distinguish between a donut and a cup,” and who work on the old Travelling Salesman problem joined UPC and BGSMath Faculty members Vera Sacristán and Rodrigo Silvera this spring for an Intensive Research Programme focussed on Discrete, Combinatorial and Computational Geometry.

Mathematics peeps out in the most unexpected ways. Say, when you have to draw a metro map. Or when you have to plan your next trip to multiple cities. Or maybe while you are enjoying an origami. Or when you have to 3D-print your favourite cup – well, when that becomes available to most people, at least. Even if you want to avoid train wagons colliding.

Rodrigo Silveira and Vera Sacristán, researchers at the UPC and BGSMath Faculty members, recently organised an Intensive Research Programme that deals with all of these problems – and much more. The programme in Discrete, Combinatorial and Computational Geometry took place at the CRM during 8 weeks between April and June 2018.

An Intensive Research Programme is “an occasion to learn, and perform research together,” to put it in Sacristán’s words. In this case, Vera and Rodrigo had put together more than 120 experts (nearly half of them, PhD students) from 19 countries in hot topics in discrete combinatorial and computational geometry – overarching topics that encompass a number of different related fields.

The research programme consisted of four different courses, and 12 different 2-hour long “inspiring lectures”, together with structured moments for participants to actively interact and do research together trying to solve open problems.

Approximation algorithms for geometric problem were at the centre of one of these courses. “There’s a famous classical example where approximation algorithms can play a role, the so-called Travelling Salesman problem,” explains Rodrigo. “How to minimise the route a salesman has to cover to visit each city and go back to the original city? Believe it or not, mathematicians do not have an efficient algorithm to solve this simple problem exactly. We can proceed geometrically, and we can maybe find a solution that is within, for example, 10% of the right one. In one of the courses, we studied these approximation algorithms,” he says.

Computational topology was another hot topic of the programme. While topology is the science that studies the deformation of geometrical objects, computational topology for example helps a 3D-printing computer to establish how to “connect” a finite set of dots in space, the input of a 3D scan. The computer has to figure out whether, say, it was a cup (with a “hole” for the handle) or a box – no holes. “The system has to figure out how points are connected to each other, how ‘persistent’ is the topology, as we say. Basically, we need to know how many holes it has”, explains Vera. Among mathematicians there’s a common joke that goes: “a topologist is someone who cannot distinguish between a donut and a cup.” The “topological” reason is clear in the image here.

Designing “optimal” graphs on a surface and the study of their intersections (themes of two other courses of the Research Programme) have some very interesting practical applications, and a sad anecdote. During World War II, in 1944, Hungarian mathematician Pál Turán was forced to work in a brick factory by the Nazis. Enslaved workers had to put bricks on small wheeled trucks to take them to storage yards. The problem was that at rail crossings generally trucks jumped off the rails, causing bricks to fall. The problem he immediately saw with mathematical eyes was: how to minimise the number of intersections? “This is a much deeper problem than it seems,” clarifies Vera. “We spent 5 days of one of the courses talking about graphs on surfaces, and how to connect vertices and edges.” An interesting and also historical application of this is in the design of maps, especially metro maps: it is far less obvious than it seems to guarantee the readability of all the station names if the network is dense.

“Our philosophy,” says Sacristán, “was to leave much room for participants to work with the lecturers on open problems in maths. New collaborations grew, and I am sure we will see some interesting publications arising soon from these working sessions.” As a sign of further interaction, many of the participants also ended up giving short seminars on their research fields.

“A very interesting aspect of the programme”, adds Rodrigo, “is computational geometry toward applications. We dedicated some lectures to this issue. For example, on geometric folding. In other words: origami. Origami has a very interesting set of industrial applications: say you want to produce a flat object that you later need to fold. These studies give you tools to understand if you can do it or not. Or say you want to inject a folded drug and want it to unfold once it gets to its target protein. We need to study what the proper folding of the molecule is.”

Two more events were included in the programme. One was the mid-term meeting of the European Project CONNECT, involving 13 universities and focussed on geometric graphs. The last week the Programme hosted the 5th Austrian Japanese Mexican Spanish Workshop on Discrete Geometry. In both cases, people gathered in to discuss open problems of the field.

The feedback Vera and Rodrigo received for the whole programme was very positive. Vera and Rodrigo believe the quality of the course was especially high, and the lectures will be published for future use. “Networking has been very powerful,” says Rodrigo. “there are not many events in these fields like this. The atmosphere was so relaxed that sharing came very spontaneously. A student even gave salsa classes, a lecturer gave squash classes: this proves that people are establishing long-lasting bonds, that will probably accompany them throughout their careers.”

Participants