Particionando um retângulo sem danificar os retângulos internos

é um retângulo paralelo ao eixo.$C$

$C_1,\dots,C_n$$C_1\cup\dots\cup C_n \subsetneq C$

Uma partição de preservação de retângulo de é uma partição , de modo que , são retângulos paralelos ao eixo separados por pares e disjuntos no interior, e para cada : , ou seja, cada retângulo existente está contido em um novo retângulo exclusivo, assim:$C$$C = E_1\cup\dots\cup E_N$$N\geq n$$E_i$$i=1,\dots,n$$C_i \subseteq E_i$

O que é um algoritmo para encontrar uma partição de preservação de retângulo com um pequeno ?$N$

Em particular, existe um algoritmo para encontrar uma partição de preservação de retângulo com partes ?$N=O(n)$

NOVA RESPOSTA: o seguinte algoritmo simples é assintoticamente ideal:

Estique cada um dos retângulos arbitrariamente, na extensão máxima possível, de modo que os retângulos permaneçam separados por pares.$C_i$

O número de furos é no máximo . Isso é assintoticamente ideal, pois há configurações nas quais o número de furos é pelo menos .$k-2$$k-O(\sqrt k)$

As provas estão neste artigo .

RESPOSTA ANTIGA:

O algoritmo a seguir, embora não seja o ideal, aparentemente é suficiente para encontrar uma partição de preservação de retângulo com partes .$N=O(n)$

O algoritmo funciona com um polígono rectilíneo , que é inicializado para o rectângulo .$P$$C$

Fase 1: Escolha um retângulo adjacente a um limite ocidental de (ou seja, não há outro retângulo entre o lado oeste de e um limite ocidental de ). Lugar dentro e esticá-lo até que ele toca a fronteira ocidental da . Seja (para ) a versão esticada de . Seja . Repita a Fase 1 vezes até que todos os$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$retângulos originais são colocados e esticados. Na imagem abaixo, uma possível ordem de colocação dos retângulos é :$C_1,C_2,C_4,C_3$

Agora, é um polígono retilíneo (possivelmente desconectado), assim:$P$

Afirmo que o número de vértices côncavos em é no máximo . Isso ocorre porque, sempre que um retângulo esticado é removido de , há 3 possibilidades:$P$$2n$$P$

• 2 novos vértices côncavos são adicionados (como ao colocar );$C_1,C_4$
• 3 novos vértices côncavos são adicionados e 1 é removido (como em );$C_3$
• 4 novos vértices côncavos são adicionados e 2 são removidos (como em ).$C_2$

Fase 2: Partição em retângulos paralelos ao eixo usando um algoritmo existente (consulte Keil 2000, páginas 10-13 e Eppstein 2009, páginas 3-5 para uma revisão).$P$

Keil cita um teorema que diz que o número de retângulos em uma partição mínima é limitado por 1 + o número de vértices côncavos. Portanto, no nosso caso, o número é no máximo e o número total de retângulos na partição é .$2n+1$$N\leq 3n+1$

Este algoritmo não é ideal. Por exemplo, no exemplo acima, fornece enquanto a solução ideal tem . Portanto, restam duas perguntas:$N=13$$N=5$

A. Este algoritmo está correto?

B. Existe um algoritmo de tempo polinomial para encontrar o ideal , ou pelo menos uma melhor aproximação?$N$