Wie bricht man eine Geometrie in Blöcke?

Ich denke dynamische Programmierung könnte dein Freund sein.

Der erste Schritt, den ich sehe, besteht darin, das Polyeder in eine triviale Sammlung von Blöcken zu unterteilen, so dass jedes mögliche Gesicht verfügbar ist (d. h. es wird in kleinste Stücke geschnitten und in Würfel geschnitten). Dies sollte trivial sein, da alles eine Achse-ausgerichtete Box ist, so dass k-Baum-ähnliche Lösungen ausreichen sollten.

Das erscheint vernünftig, weil ich auf seine Kosten schauen kann. Die Kosten dafür sind, dass ich die ursprüngliche Konfiguration von Hyperslabs "vergesse", indem ich sie durch eine neue Reihe von Hyperslabs ersetze. Der einzige Weg, der mich in die Irre führen könnte, ist, wenn die ursprüngliche Konfiguration etwas für die Lösung zu bieten hat. Da Sie eine "optimale" Lösung für alle Konfigurationen wünschen, müssen wir davon ausgehen, dass die ursprüngliche Struktur nicht sehr hilfreich ist. Ich weiß nicht, ob es bewiesen werden kann, dass diese ursprüngliche Information nutzlos ist, aber ich werde diese Annahme in dieser Antwort machen.

Das Problem wurde nun auf ein Grafikproblem reduziert, das einem Constrained-Spanning-Forest-Problem ähnelt. Ich denke, die natürlichste Art, das Problem zu betrachten, besteht darin, es als ein Graphik-Färbungsproblem zu betrachten (so lange man es vermeiden kann, es mit dem bekannteren Graph-Färbungsproblem zu verwechseln, wenn man versucht, eine Karte ohne zwei Zustände der gleichen Farbgebung zu färben eine Grenze). Ich habe ein Diagramm von Knoten (kleine Blöcke), denen ich jeweils eine Farbe zuweisen möchte (die schließlich das "Hyperslab" sein wird, das diesen Block abdeckt). Ich habe die Einschränkung, dass ich Farben in hyperslab Formen zuweisen muss.

Nun eine wichtige Beobachtung ist, dass nicht alle Möglichkeiten berücksichtigt werden müssen. Nimm das letzte farbige Diagramm, das wir sehen wollen. Wir können diesen Graphen beliebig partitionieren, indem wir ein Hyperslab, das die Partition in zwei Teile teilt, aufbrechen. Nicht jede Partition ist jedoch sinnvoll. Die einzigen Partitionen, die Sinn ergeben, sind Achsen-ausgerichtete Schnitte, die ein Hyper-Slab immer in zwei Hyper-Slabs aufspalten (im Gegensatz zu irgendeiner komplizierteren Form, die auftreten könnte, wenn der Schnitt nicht mit der Achse ausgerichtet wäre).

Jetzt ist dieser Schnitt die Umkehrung des Problems, das wir wirklich zu lösen versuchen. Dieses Schneiden ist eigentlich das, was wir im ersten Schritt gemacht haben. Wir möchten zwar den optimalen Algorithmus zum Zusammenführen finden und diese Schnitte rückgängig machen. Dies zeigt jedoch ein Schlüsselmerkmal, das wir bei der dynamischen Programmierung verwenden werden: Die einzigen Merkmale, die für das Zusammenführen wichtig sind, sind auf der freiliegenden Oberfläche eines Schnitts. Sobald wir die optimale Art gefunden haben, die zentrale Region zu bilden, spielt sie im Allgemeinen keine Rolle.

Beginnen wir also damit, eine Sammlung von Hyperslab-Räumen zu erstellen, die nicht nur ein einfaches Hyperslab definieren können, sondern auch beliebige Konfigurationen von Hyperslabs wie solchen mit Löchern. Jeder hyperslab-Raum zeichnet auf:

• Die Anzahl der darin enthaltenen Blatthyperlabs (dies ist die Zahl, die wir versuchen werden zu minimieren)
• Die interne Konfiguration von hyperslabs.
• Eine Karte der Oberfläche des Hyperslab-Raums, die zum Zusammenführen verwendet werden kann.

Wir definieren dann eine "merge" -Regel, um zwei oder mehr benachbarte hyperslab-Räume in eins zu verwandeln:

• Hyperslab-Räume können nur zu neuen Hyperslab-Räumen kombiniert werden (daher müssen Sie genügend Teile kombinieren, um ein neues Hyperslab zu erzeugen, nicht eine exotischere Form)
• Zusammenführungen werden einfach durch Vergleichen der Oberflächen durchgeführt. Wenn Features mit übereinstimmenden Dimensionen vorhanden sind, werden sie zusammengeführt (weil es trivial ist, zu zeigen, dass es bei Übereinstimmung der Features immer besser ist, hyperslabs zu verschmelzen als nicht)

Jetzt ist das genug, um das Problem mit roher Gewalt zu lösen. Die Lösung wird mit Sicherheit NP-vollständig sein. Wir können jedoch eine zusätzliche Regel hinzufügen, die diese Kosten dramatisch senkt: "Ein Hyperslab-Raum wird als" besser "angesehen als ein anderer, wenn er den gleichen Raum abdeckt und genau dieselben Merkmale auf seiner Oberfläche hat mit weniger Hyperslabs drin ist es die bessere Wahl. "

Nun ist die Idee hier, dass Sie früh im Algorithmus alle Arten von Kombinationen im Auge behalten müssen, nur für den Fall, dass sie am nützlichsten sind. Da jedoch der Zusammenführungsalgorithmus die Dinge größer und größer macht, wird es weniger wahrscheinlich, dass interne Details auf der Oberfläche des Hyperslab-Raums exponiert werden. Bedenken Sie

Sieh dir die linke Seitenbox an, die ich in stärkeren Linien markieren durfte. Wenn es darum geht, Boxen mit dem Rest der Welt zu verschmelzen, ist die AB: XY-Oberfläche alles, worauf es ankommt. Daher gibt es nur eine Handvoll von Zusammenführungsmustern, die an dieser Oberfläche auftreten können

• Keine Zusammenführung möglich
• A: X erlaubt das Zusammenführen, aber B: Y nicht
• B: Y erlaubt das Zusammenführen, aber A: X nicht
• Sowohl A: X als auch B: Y erlauben das Zusammenführen (zwei unabhängige Zusammenführungen)
• Wir können ein größeres Quadrat, AB: XY
zusammenführen

Es gibt viele Möglichkeiten, das 3x3-Quadrat zu bedecken (mindestens ein paar Dutzend).Wir müssen uns jedoch nur daran erinnern, wie Sie diese Merge-Prozesse am besten erreichen können. Sobald wir diesen Punkt in der dynamischen Programmierung erreicht haben, können wir alle anderen möglichen Kombinationen vergessen und uns nur auf den besten Weg konzentrieren, um die einzelnen Oberflächenfunktionen zu erreichen.

Tatsächlich stellt dies das Problem für einen leicht gierigen Algorithmus dar, der untersucht, welche Zusammenführungen das beste Versprechen zur Verringerung der Anzahl von Hyperslabs liefern, wobei immer daran erinnert wird, wie eine gegebene Menge von Oberflächenmerkmalen am besten erreicht werden kann. Wenn der Algorithmus fertig zusammengeführt wird, ist der optimale Layout, unabhängig vom endgültigen Hyperlab-Raum.

Ich weiß nicht, ob es beweisbar ist, aber mein Bauchgefühl glaubt, dass dies ein O (n ^ d) -Algorithmus sein wird, wobei d die Anzahl der Dimensionen ist. Ich denke, die Worst-Case-Lösung wäre eine Sammlung von Hyperslabs, die zusammen ein großes Hyperslab bilden. In diesem Fall glaube ich, dass der Algorithmus sich schließlich in die Umkehrung eines k-Baum-Algorithmus einarbeiten wird. Auch hier gibt es keinen Beweis ... es ist nur mein Bauchgefühl.