The Lawn Mowing Problem

From Algebra to Algorithms


(Fekete et al. 2023)

Continuous generalization of the traveling salesman problem (TSP).

Tour starts and ends at the same point, covers every point.


  • Galois groups
  • Abelian property
  • Polyminoes
  • Minkowski sums

Galois groups

Polynomials are solvable by radicals iff they have enough symmetry.

i.e. iff their Galois group is abelian (commutative)

Polynomials of order < 5 are algebraically easy

  • Can be solved by radicals

\( \frac{-b \pm \sqrt{b^2-4ac}}{2a} \)

Most polynomials of order ≥ 5 are algebraically hard

  • Cannot be solved by radicals


Generalized dominoes.


Shapes made up of pixels.

Minkowski sums

\( {\color{red} R} = {\color{green} G} \bigoplus {\color{blue} B} = \{ \mathbf g + \mathbf b\ |\ \mathbf g \in {\color{green} G},\ \mathbf b \in {\color{blue} B} \} \)

Minkowski sum.svg

Real world


Efficient covering of polyminoes

different kinds of TSPs.svg

Efficient covering of pixels

pixel coverings.svg

Traveling Salesperson

Problem is now reduced to the traveling salesperson problem. Solution:

  • Integer Programming (IP)
  • Large Neighborhood Search (LNS)

Lower & Upper Bounds

bounds comparison.svg


Already proven:

  • the optimal tour of a polygon is polygonal itself

Proven in this paper

  • the coordinates are algebraically hard

Future research:

  • Better lower bounds


Fekete, Sándor P., Dominik Krupke, Michael Perk, Christian Rieck, and Christian Scheffer. 2023. “The Lawn Mowing Problem: From Algebra to Algorithms.” 2023.