1 Team UBC, Canada: Da Wei Zheng, Jack Spalding-Jamieson, Brandon Zhang
| Total score | Best solutions (from 346 instances) | Unique best solutions |
| 175.172880 | 209 | 11 |
All members of this team were students, so they also won the Junior Category.
The Minimum Convex Partition problem (MCP) is a problem in which a point-set is used as the vertices for a planar subdivision, whose number of edges is to be minimized. In this planar subdivision, the outer face is the convex hull of the point-set, and the interior faces are convex. In this paper, we discuss and implement the approach to this problem using randomized local search, and different initialization techniques based on maximizing collinearity. We also solve small instances optimally using a SAT formulation. We explored this as part of the 2020 Computational Geometry Challenge, where we placed first as Team UBC.
2 Team Haute-Alsace, France: Laurent Moalic, Dominique Schmitt, Julien Lepagnot, Julien Kritter
| Total score | Best solutions (from 346 instances) | Unique best solutions |
| 175.130597 | 297 | 126 |
We present a memetic approach designed to tackle the 2020 Computational Geometry Challenge on the Minimum Convex Partition problem. It is based on a simple local search algorithm hybridized with a genetic approach. The population is brought down to its smallest possible size - only 2 individuals - for a very simple implementation. This algorithm was applied to all the instances, without any specific parameterization or adaptation.
3 Team Salzburg, Austria: Günther Eder, Martin Held, Stefan de Lorenzo, Peter Palfrader
| Total score | Best solutions (from 346 instances) | Unique best solutions |
| 175.040207 | 187 | 0 |
Our work on minimum convex decompositions is based on two key components: (1) different strategies for computing initial decompositions, partly adapted to the characteristics of the input data, and (2) local optimizations for reducing the number of convex faces of a decomposition. We discuss our main heuristics and show how they helped to reduce the face count.
H Honorable mention: Team Les Shadoks, France: Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, Aldo González-Lorenzo
| Total score | Best solutions (from 346 instances) | Unique best solutions |
| 174.695586 | 160 | 6 |
