Apptus Blog

Reflections on EuroCG 2017 - The Computational Geometry Event

Written by Nilla Hedlund | Apr 18, 2017

Between the 5th and 7th April Apptus sponsored the European computational geometry conference (EuroCG). The conference travels from city to city in Europe. This year it was hosted by Malmö University for the first time. Mikael Hammar, head of the research team at Apptus Technologies, wrote an interesting blog piece about it.

The computational geometry community

Researchers in computational geometry form a small community. I was a member while doing my PhD at Lund University but lost track of it when I changed career and started working on graph theory and later with information retrieval and recommender algorithms in the private sector. The conference gave me the chance to catch up with some friends and former colleagues.

My name is Mikael Hammar, I head the research team at Apptus Technologies. I have been asked to contribute to our company blog for some time now, but I have always had some other important stuff to attend to, such as working on the release of our new recommender system, discussing research related topics with our customers and partners or assisting our product manager with strategic product planning.

Now that Apptus had taken the opportunity to support the data science community in the region by sponsoring EuroCG, I thought it would be a good day to start contributing.

The conference deals with problems in computational geometry (CG for short). This year it was hosted by Bengt J. Nilsson at Malmö University. Bengt was my advisor during my PhD studies, and we have collaborated ever since, working mainly on recommender systems theory. Currently we are collaborating on a research project funded by the Vinnova Foundation. Bengt is a well-respected member of the CG community. The response he got from the audience at this event's closing remarks was emotional to say the least.

The computational geometry goal

Traditionally, the CG community studies esoteric problems in computational geometry; a sub category of algorithms’ theory. The goal is to come up with algorithms for which you can give certain general performance guarantees. What do I mean by that?

Well, it's not enough to find a so-called heuristic, that is, an algorithm that works most of the time - although it’s unclear how well and in which situations. Rather we are looking for well-defined algorithms with guaranteed execution times.

At the conference, I had the great pleasure to speak with Håkan Jonsson from Luleå Technical University. Håkan is a CG member that has brought computational geometry into the mining industry. He made driverless trucks possible long before Google and Tesla. In the late nineties LKAB used driverless trucks in its mines, thanks to Håkan's research. I hadn't seen him in 16 years, so it was great to spend some time during the coffee breaks catching up.

Håkan Jonsson (right) explains Pokémon Go to Bengt J. Nilsson (left)
after a talk on the subject by Mark van Kreveld at EuroCG 2017 at Malmö University.

Problem solving and ‘play’ in computational geometry

In the early days, Håkan explained, this research community had a playful approach to problem solving. But the field has evolved towards a more serious, and mathematically challenging direction.

I agree with Håkan and recall Joseph O'Rourke and his research team, who played games while solving problems - which was very refreshing to see. It felt almost like a game of Sudoku when they attacked a research problem. From this group, I've learned that the best way to attack difficult problems is to play around with them and not taking things too seriously.

Another great mind in CG is Joseph Mitchell. He visited the conference this year, and gave an inspiring talk that summarised research on three major topics in computational geometry: the travelling salesman problem, art gallery problems, and shortest watchman route problems.

These were also the problems I studied as a PhD student. In fact, Joe Mitchell was the opponent of my PhD thesis, and it was wonderful to be reunited with him at this conference after a 15-year absence.
The problems Joe presented are of great importance today. Art gallery problems are related to base station placements and Wi-Fi modem-placements in buildings. Basically, you want to place as few stations or modems as possible and still have full coverage. In the art gallery problem, we try to find out how many stations are needed and how to place them to get full coverage.

The name comes from the original application, where you want to place guards in an art gallery so that they together can see the entire gallery. This problem appeared on the TV show Numb3rs (episode 3 in season 2 called "Obsession"), in which Charlie Eppes explains that, in 1973, Viktor Klee posed the problem for Chvatal, who then went on to prove upper and lower bounds on the number of guards necessary.

Kinetic data structures

Another research area within computational geometry is that of kinetic data structures. This area was initially studied in the 80s and gained traction in the late 90s.

An expert in the field, Mark de Berg from the University of Eindhoven studies the problem of maintaining efficient data structures for objects in motion - where a typical application is in collision detection, especially for airline traffic control.

Another application helps marketers communicate with people using pop-up notices on cell phones, typically to send targeted ads when a person enters the vicinities of a store. To be able to achieve this, you need to track people using GPS signals. This is a typical problem within computational geometry, and especially kinetic data structures.

Bettina Speckmann, also from the University of Eindhoven gave a talk on kinetic data structures on Thursday morning. She presented different problem variations, which can be used to understand to which group a person or an entity belongs as it moves, based on common parameters such as position, distance and speed.

Computational Geometry and eCommerce

With this final example I hope that I made clear the connection between Apptus and EuroCG. Specifically, we gained insights in new techniques and applications close to our own problem sphere; the eCommerce business and automated marketing.

But the main reason for the sponsorship is to make the conference affordable for PhD-students.
This type of sponsorship is important for the research community. After all the economic reality for PhD-students doing pure science is common knowledge - so, If we can help them just a little bit on their path, we are all the merrier.

Mikael Hammar