https://cgshop.ibr.cs.tu-bs.de/competition/cg-shop-2027/#problem-description
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.
Best wishes,
Sándor Fekete on behalf of the Challenge team