Rasenmäherproblem

Das Rasenmäherproblem ist ein Problem in der algorithmischen Geometrie. Anschaulich wird gefragt, wie man zu einer gegebenen Fläche (einem „Rasen“) und einem gegebenen Rasenmäher eine Route bestimmt, die den ganzen Rasen mäht und dabei die kürzeste unter allen möglichen Routen ist.

Zur Formalisierung definiert man sich folgende Begriffe:

Gegeben ein Gebiet (ein Rasen) $R\subseteq \mathbb {R} ^{2}$. Per Diskretisierung nehmen wir an, dass $R$ aus endlich vielen mehrfach zusammenhängenden polygonalen Komponenten besteht. Notiere mit $n$ die Anzahl der Ecken und mit $\delta R$ den Rand von $R$. Sei außerdem ein Rasenmäher $\chi$, das heißt ein Polygon um einen Koordinatenursprung, gegeben. Bezeichne für ein $p\in \mathbb {R} ^{2}$ mit $\chi (p)$ die Platzierung von $\chi$ in $p$, das heißt die Parallelverschiebung von $\chi$ um den Ortsvektor von $p$.

• Eine Schneidetour ist dann eine Kurve $\pi$, für die jeder Punkt aus $R$ durch eine Platzierung aus $\pi$ überdeckt wird. Es gilt also $R\subseteq \cup _{p\in \pi }\chi (p)$ (S).

• Manchmal ist man auch an einer Fräsetour interessiert. Damit ist eine Schneidetour gemeint, die keinen Punkt außerhalb von $R$ „mäht“, das heißt, es gilt (S) mit Gleichheit.
• Das Rasenmäherproblem fragt nach einer Schneidetour mit minimaler Länge. Das Fräsungsproblem fragt nach einer minimalen Fräsetour oder alternativ nach einem Beweis dafür, dass keine Fräsetour existiert.

Obwohl für den Rasenmäher viele Figuren denkbar wären, sind praktisch nur das Einheitsquadrat und der Einheitskreis als Rasenmäher interessant und gut untersucht.

• Einfache Beobachtungen
• 
  (Abb. 1) Das Fräsungsproblem
• 
  (Abb. 2) Für kombinatorisch sehr einfache Rasenflächen (hier $n=4$) kann die kombinatorische Darstellung der kürzesten Schneidetour potentiell unbegrenzt groß sein.
• 
  (Abb. 3) Achsenparalleles Rasenmähen und …
• 
  (Abb. 4) … kantenparalleles Rasenmähen.

Wegen des Phänomens, das in Abbildung 2 illustriert wird, definiert man die Komplexität einer Eingangsgröße des Rasenmäherproblems nicht als $n$, sondern als die Länge einer Zahlendarstellung der Koordinaten der Eckpunkte von $R$. Mit diesem Verständnis der Eingangsgröße lassen sich Pseudopolynomielle Algorithmen finden, die das Rasenmäherproblem lösen.

Arkin, Fekete & Mitchell (2000) schlagen für das Rasenmäherproblem eine Reduktion auf das Hamiltonkreisproblem in planaren bipartiten Graphen mit Maximalgrad 3 vor. Sie zitieren dann das Argument von Johnson & Papadimitriou (1985), um zu beweisen, dass das Rasenmäherproblem schon für Polygone NP-schwer ist. Dasselbe Argument wenden sie auch auf das Fräsungsproblem an, können dort aber nur zeigen, dass es für mehrfach zusammenhängende polygonale Gebiete NP-schwer ist. Sie schlagen außerdem einen einfachen Approximationsalgorithmus für beide Probleme vor:

Überdeckung der Ebene mit kreisförmigen Pixeln. Eingezeichnet ist eine Lösung des Rundreiseproblems im Graphen $S$. Die optimale Rundreise liefert eine Approximation für das Rasenmäherproblem bei kreisförmigem Rasenmäher.

1. Bestimme einen Gittergraphen $S$ so, dass $S$ die Mittelpunkte derjenigen Pixel enthält, die mit $R$ schneiden.
2. Benutze eine bekannte Approximationsmethode für das Rundreiseproblem.

Schritt 1 hat eine Laufzeit von ${\mathcal {O}}(s\log s)$, dabei ist $s$ die Mächtigkeit von $S$.

Literatur

• E.M. Arkin, S.P. Fekete, J.S.B. Mitchell: Approximation algorithms for lawn mowing and milling. In: Computational Geometry. 17. Jahrgang, Nr. 1–2, 2000, S. 25–50 (edu.au [PDF]). 
• D.S. Johnson, C.H. Papadimitriou: The Traveling Salesman Problem. John-Wiley and Sons, Ltd., 1985, ISBN 0-471-90413-9, Computational complexity, S. 37–86.