Ein Rechteck partitionieren, ohne innere Rechtecke zu beschädigen

$C$ ist ein achsparalleles Rechteck.

$C_1,\dots,C_n$ sind achsparallele Rechtecke die paarweise im Inneren getrennt sind, so dass wie :$C_1\cup\dots\cup C_n \subsetneq C$

Eine rechteckerhaltende Partition von $C$ ist eine Partition $C = E_1\cup\dots\cup E_N$ , so dass $N\geq n$ , die $E_i$ achsparallele Rechtecke sind, und für jedes $i=1,\dots,n$ : $C_i \subseteq E_i$ , dh jedes vorhandene Rechteck ist in einem eindeutigen neuen Rechteck enthalten, wie folgt:

Was ist ein Algorithmus zum Auffinden einer rechteckbewahrenden Partition mit einem kleinen ?$N$

Gibt es insbesondere einen Algorithmus zum Auffinden einer rechteckerhaltenden Partition mit Teilen?$N=O(n)$

NEUE ANTWORT: Der folgende einfache Algorithmus ist asymptotisch optimal:

Dehnen Sie jedes der Rechtecke beliebig, so dass die Rechtecke paarweise disjunkt bleiben.$C_i$

Die Anzahl der Löcher beträgt höchstens . Dies ist asymptotisch optimal, da es Konfigurationen gibt, bei denen die Anzahl der Löcher mindestens beträgt .$k-2$$k-O(\sqrt k)$

Die Beweise sind in diesem Papier .

ALTE ANTWORT:

Der folgende Algorithmus ist zwar nicht optimal, aber anscheinend ausreichend, um eine rechteckerhaltende Partition mit Teilen zu finden.$N=O(n)$

Der Algorithmus arbeitet mit einem geradlinigen Polygon , das auf das Rechteck initialisiert wird .$P$$C$

Phase 1: Wähle ein Rechteck das an eine Westgrenze von angrenzt (dh es gibt kein anderes Rechteck zwischen der Westseite von und einer Westgrenze von ). Platziere in und dehne es, bis es die westliche Grenze von berührt . Sei (für ) die gedehnte Version von . Sei . Wiederholen Sie Phase 1 mal, bis alle$C_i$$P$$C_j$$C_i$$P$$C_i$$P$$P$$E_i$$i=1,\dots,n$$C_i$$P=P\setminus E_i$$n$$n$C 1 , C 2 , C 4 , C 3Die ursprünglichen Rechtecke werden platziert und gedehnt. In der folgenden Abbildung ist eine mögliche Reihenfolge für das Platzieren der Rechtecke :$C_1,C_2,C_4,C_3$

Nun ist ein geradliniges Polygon (möglicherweise nicht verbunden), wie folgt:$P$

Ich behaupte, dass die Anzahl der konkaven Ecken in höchstens . Dies liegt daran, dass es drei Möglichkeiten gibt , wenn ein gestrecktes Rechteck aus entfernt wird :$P$$2n$$P$

• 2 neue konkave Eckpunkte werden hinzugefügt (wie beim Platzieren von );$C_1,C_4$
• 3 neue konkave Eckpunkte werden hinzugefügt und 1 wird entfernt (wie bei );$C_3$
• Es werden 4 neue konkave Eckpunkte hinzugefügt und 2 entfernt (wie bei ).$C_2$

Phase 2: Partitionieren von in achsparallele Rechtecke unter Verwendung eines vorhandenen Algorithmus ( eine Übersicht finden Sie in Keil 2000, Seite 10-13 und Eppstein 2009, Seite 3-5 ).$P$

Keil zitiert einen Satz, der besagt, dass die Anzahl der Rechtecke in einer minimalen Partition durch 1 + die Anzahl der konkaven Scheitelpunkte begrenzt ist. In unserem Fall beträgt die Anzahl daher höchstens , und die Gesamtzahl der Rechtecke in der Partition beträgt .$2n+1$$N\leq 3n+1$

Dieser Algorithmus ist nicht optimal. Im obigen Beispiel ist beispielsweise während die optimale Lösung . Es bleiben also zwei Fragen:$N=13$$N=5$

A. Ist dieser Algorithmus korrekt?

B. Gibt es einen Polynom-Zeit-Algorithmus, um das optimale , oder zumindest eine bessere Näherung?$N$