Bachelor Project at BARC wins Computational Geometry Challenge
Bachelor student William Bille Meyling, and BARC researchers Mikkel Abrahamsen and André Nusser were announced as winners of the CG:Shop 2023 challenge coming out first at the most important implementation challenge in computational geometry.
Bachelor Project at BARC wins Computational Geometry Challenge
On January 27th, 2023, a team consisting of BA student William Bille Meyling and BARC researchers Mikkel Abrahamsen, and André Nusser were announced as winners of the CG:Shop 2023 challenge coming out first out of 18 participating teams at the most important implementation challenge in computational geometry.
This challenge is co-located with the flagship conference in the field of computational geometry; the International Symposium on Computational Geometry (SoCG)
While it was a head-to-head race for first place with another team, the remaining teams obtained results that were significantly outperformed.
To add to this feat, the work was conducted as part of William’s Bachelor project. He did all the implementation work without having significant prior experience in computational geometry. Mikkel and André supplied ideas with their expertise in computational geometry and algorithm engineering.
The problem of the challenge was to cover a given polygon with the smallest number of convex pieces. For more than 200 instances ranging from small to huge polygons, points were given based on how small the solution that was found by the respective team.
The left side shows one of the (smallest) input instances, a polygon with holes. The right side shows the convex cover that their algorithm computes. Note how the algorithm cleverly exploits that the polygons of the cover can overlap to find a solution of small size.
Interestingly, Mikkel proved this problem extremely hard to solve exactly in theory in previous work, published at the Symposium on Foundations of Computer Science (FOCS). This challenge was an endeavor to investigate how difficult this problem is to solve in practice. While it remains very difficult to find the smallest existing solutions, it was possible to find surprisingly small and intricate solutions with their approach that is a clever combination of tools from computational geometry and graph algorithms.
Using this approach, they were able to obtain great solutions for instances with more than a hundred thousand vertices.
One of the medium-sized instances of the challenge (left) with the cover that their algorithm computes (right)Their implementation used only free and open source software, which will make their solver freely and publicly available. As winners of the challenge, they are invited to present their work at the International Symposium on Computational Geometry (SoCG) 2023 in Dallas (USA) in June.