[DMANET] First Announcement: CG Challenge 2027 - Lawn Mowing

Dear friends and colleagues, The new problem for the CG Challenge 2027 has been chosen: We will ask you to engage in lawn mowing! For a given polygonal region P, the Lawn Mowing Problem (LMP) asks for a shortest tour T that gets within Euclidean distance 1/2 of every point in P; this is equivalent to computing a shortest tour for a unit-diameter cutter C that covers all of P. As a generalization of the Traveling Salesman Problem, the LMP is NP-hard; it is also closely related to the Traveling Salesman Problem with Neighborhoods, for which it suffices to visit the vicinity of points rather than the points themselves. Unlike the discrete TSP, the LMP has long defied efforts to achieve exact solutions, due to its combination of combinatorial complexity with continuous geometry, so that only recent time has seen some practical progress. One of the challenges of dealing with Euclidean LMP instances are complications from difficult coordinates, making feasibility itself quite tricky to achieve and check. We will address this by restricting instances to polyominoes, with the cutter being a smaller polyomino that moves in an axis-parallel fashion. We are hopeful that this will make the problem interesting to both student groups and experienced researchers. More details will be posted by mid August. Stay tuned! Best wishes, Sándor Fekete on behalf of the Challenge team ********************************************************** * * Contributions to be spread via DMANET are submitted to * * DMANET@zpr.uni-koeln.de * * Replies to a message carried on DMANET should NOT be * addressed to DMANET but to the original sender. The * original sender, however, is invited to prepare an * update of the replies received and to communicate it * via DMANET. * * DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET) * http://www.zaik.uni-koeln.de/AFS/publications/dmanet/ * **********************************************************