Polyominos: Theorem von Golomb bent strip -> strip

Erste Frage Aufrufe: 211     Aktiv: 04.02.2024 um 16:53

1

Hallo,

es geht mir speziell um die Anwendung des Satzes von Golomb, in dem er sagt, dass aus jedem "gebogenen Streifen" (BS) ein "Streifen" (S) generiert werden kann. Dies sagt er bezugnehmend auf seine "Tiling Hierarchy".

Ich habe bisher, trotz diverser englischer Quellen nicht verstanden, wie das ganze umgesetzt werden kann, vielleicht liegt es ja auch an einem Übersetzungs-/Verständnisfehler. An einer anderen Stelle hatte ich gelesen, dass es eher ein theoretisches Verfahren ist. Ich bin selbst eher praktisch veranlagt und habe es mir wohl bisher falsch vorgestellt.

Laut seiner Erklärung soll eine rechteckige Hülle um das eigentliche Polyomino gelegt werden und dann in regelmäßigen Abständen nach einem identischen Teil gesucht werden. Wie aber dies geschieht und dieser "schnitt" durch den Arm verstehe ich nicht.

Über eine Erklärung und ein Beispiel, wenn möglich, würde ich mich freuen.

Vielen Dank an alle helfenden.

gefragt

Punkte: 21

 

Das bedeutet also auch, dass ich den Abschnitt nicht an den vorherigen gebogenen Streifen Ansätze, sondern einfach aus dem gebogenen einen neuen Streifen generiere, Ist das richtig? Ich hatte mir das immer bildlich so vorgestellt und hatte dann einen Streifen, an dem die Reste von dem gebogenen Streifen hängen :D   ─   ich123 02.02.2024 um 20:32
Kommentar schreiben
2 Antworten
1
Ich vollziehe mal den Beweis von Theorem 3 von Tiling with Polyominoes anhand des folgenden Polyomino A nach:

Wie in Fig. 7 dieses Artikes zu sehen ist, kann man damit den "Bended strip" pflastern, A gehört also zur Klasse (BS).
Nun muss man zeigen, dass A auch zu (S) gehört - was intuitiv klar ist, aber eben auch durch das Theorem 3 gezeigt werden kann.

Dort ist die Rede von einer "rectangular hull", also einem Rechteck, was A fassen kann. Damit ist folgendes Rechteck gemeint:

Dieses hat die "dimension" \(2\cdot 3\), also ist m=3 die maximale "dimension" dieses Rechteckes.
w ist die Breite eines Armes des "bended strip". Beide Arme des "bended strip" aus Fig. 7 haben die Breite 2. Also ist w=2.

Nun nehme ich mal den waagrechten Arm dieses "bended strips". Aus diesem Arm schneide ich ein Stück der Länge m=3 heraus. Und nun ist die Behauptung, dass ich immer einen Weg von oben nach unten durch dieses Stück finde, welches nicht durch das Polyomino geht. Das ist klar, denn A hat ja nur die Länge 3. Und Fig. 7 zeigt das auch.

Und nun ist, dass die Wege von oben nach unten nur auf endlich verschiedene Arten geformt sein können, denn das rechteckige Stück, auf dem sich der Weg bewegt, ist ja endlich. In unseren Beispiel gibt es nur folgenden Weg:

Deswegen muss sich der so geformte Weg irgendwann wiederholen.
In unserem Beispiel wiederholt sich dieser Weg alle 2 Einheitslängen.
Und nun nimmt man das Stück zwischen zwei gleich gestalteten Wegen - das ist hier wieder das Polyomino A.
Diese Stücke sind oben und unten durch gerade Linien begrenzt, und rechts und links durch die gleich geformte Begrenzung.
Und deswegen kann mit diesem Stück dann einen "stripe" zusammensetzen.


Diese Antwort melden
geantwortet

Punkte: 2.31K

 

Vielen Dank, das ist super verständlich.   ─   ich123 02.02.2024 um 20:24

Noch eine "blöde" Frage, die aber dennoch gestellt werden kann. Wieso könnte ich nicht einfach sagen: Ich schneide von oben nach unten mit einem graden Schnitt? Golomb sagt ja, dass das Polyomino nicht zerschnitten werden darf, gibt es dafür aber eine sinnige Erklärung?

Ich hätte jetzt gesagt, da ich den Strip ja mit dem Polyomino A parkettieren möchte und dies mit einer geraden Kante nicht geht.
  ─   ich123 03.02.2024 um 12:07

Naja, wenn ich aus einem Arm ein Stück der Länge m herausschneide, tue ich das mit einem geraden Schnitt. Siehe auch die Bilder von onetimeuser. Dort sieht man blaue und grüne Segmente, die rechts und links durch gerade Schnitte begrenzt sind.

Später im Beweis komme ich natürlich mit diesen geraden Schnitten nicht mehr hin, denn brauche ich Stücke, die aus ganzen, also unzerschnittenen Polyominos bestehen. Ich brauche also Schnitte, die nicht durch Polyominos hindurchgehen.
  ─   m.simon.539 03.02.2024 um 19:54

Kommentar schreiben

0

Hier wäre ein grafisches Beispiel mit einem W-Polyomino. Hätte eigentlich gerne einen Kommentar auf die antwort von m.simon geschrieben, aber da kann ich leider kein Bild einbetten.
Diese Antwort melden
geantwortet

Punkte: 45

 

Vielen Dank, darf ich fragen aus welcher Quelle die Bilder kommen?   ─   ich123 02.02.2024 um 20:25

Mit Inkscape selber erstellt, deshalb ist die Textgröße so inkonsistent :). Inspiration für das spezifische Tiling kommt von aus Figure 6 von dem Paper hier https://api.semanticscholar.org/CorpusID:126386911   ─   onetimeuser 02.02.2024 um 20:45

Vielen Dank, das kannte ich noch nicht.   ─   ich123 03.02.2024 um 12:08

Hallo onetimeuser,

eine Frage noch. Wenn ich das richtig verstanden habe müssten in deinem Beispiel doch die Segmente in der Größe 3*5 geschnitten werden und in denen dann ein Polgonzug von oben nach unten gezeichnet werden. Wenn ich das in deiner Grafik jetzt richtig sehe, sind die Segmente aber 4 Quadrate breit. Hat sich da jetzt ein Fehler eingeschlichen, kann ich nicht richtig gucken oder habe ich es doch nicht verstanden?
Vielen lieben Dank für eure Hilfe.
  ─   ich123 04.02.2024 um 16:53

Kommentar schreiben