Retângulos de embalagem em polígonos convexos, mas sem rotações

23

Estou interessado no problema de empacotar cópias idênticas de retângulos (bidimensionais) em um polígono convexo (bidimensional) sem sobreposições. No meu problema, você não tem permissão para girar os retângulos e pode assumir que eles estão orientados paralelamente aos eixos. Você recebe as dimensões de um retângulo e os vértices do polígono e pergunta quantas cópias idênticas do retângulo podem ser empacotadas no polígono. Se você tem permissão para girar os retângulos, esse problema é conhecido como NP-hard, acredito. No entanto, o que se sabe se você não pode? E se o polígono convexo for simplesmente um triângulo? Existem algoritmos de aproximação conhecidos se o problema é realmente NP-difícil?

Resumo até agora (21 de março de 11). Peter Shor observa que podemos considerar esse problema como um dos quadrados da unidade de empacotamento em um polígono convexo e que esse problema está no NP se você impuser um limite polinomial ao número de quadrados / retângulos a serem empacotados. Sariel Har-Peled ressalta que existe um PTAS para o mesmo caso polinomialmente limitado. No entanto, em geral, o número de quadrados empacotados pode ser exponencial no tamanho da entrada, que consiste apenas em uma lista possivelmente curta de pares de números inteiros. As seguintes perguntas parecem estar abertas.

A versão completa e ilimitada está no NP? Existe um PTAS para a versão ilimitada? O caso polinomialmente delimitado está em P ou NPC? E meu favorito pessoal, o problema é mais fácil se você apenas se limitar a empacotar quadrados de unidades em um triângulo?

Rafael
fonte
Embalar com retângulos 1x3 é NP-completo (com rotação) e acho que fica fácil se proibirmos as rotações. Você encontra o número máximo de retângulos para cada linha (ou colunas) e os adiciona para obter o número máximo geral de retângulos compactados.
Mohammad Al-Turkistany
Não tenho certeza de que corrigir as dimensões em 1x3 (ou qualquer outra coisa) ajude muito para o meu problema, não é? O polígono convexo não tem necessariamente nenhum lado paralelo aos eixos e você ainda precisa decidir onde colocar os retângulos. Você pode colocá-los mais baixos no eixo y primeiro e depois justificados à esquerda como uma heurística razoável, mas você pode construir exemplos com bastante facilidade onde isso não é o ideal.
Raphael
9
Você pode aplicar uma transformação afim para tornar todos os retângulos . Portanto, o problema é equivalente ao de empacotar quadrados. 1×1
Peter Shor
1
@turkistany: Você poderia me dar uma referência que mostre a completude do NP para retângulos 1x3? Ou é fácil de observar?
Yoshio Okamoto
3
Pesquisando com base na observação de Peter Shor, maven.smith.edu/~orourke/TOPP/P56.html aparece, o que é interessante. No entanto, parece estar focado em polígonos simples gerais (ou seja, podem ser côncavos).
Raphael

Respostas:

12

O problema pode ser reformulado como escolher um número máximo de pontos dentro de um polígono convexo, de modo que a cada par deles é na distância (sob a métrica) pelo menos 1 entre si (basta pensar sobre os centros dos quadrados) . Por sua vez, isso está relacionado ao mesmo problema em que se usa a distância euclidiana regular. Por sua vez, isso está relacionado à criação de malhas, onde se interessa em dividir um polígono em regiões bem comportadas (ou seja, você toma o diagrama de Voronoi dos centros [ver mosaicos de Centoral Voronoi]).L1

De qualquer forma, um aproximação ϵ ) é bastante fácil. Você desliza aleatoriamente uma grade do comprimento lateral S ( 1 / ϵ ) . Prenda o polígono na grade e resolva o problema dentro de cada parte da interseção do polígono com a grade usando força bruta. Um algoritmo com tempo de execução O ( M n o i s e ( ϵ ) ) deve seguir facilmente, onde M é o número de pontos (ou seja, retângulos) e n o i s e ( ϵ )(1ϵ)O(1/ϵ)O(Mnoise(ϵ))Mnoise(ϵ)é uma função horrenda que depende apenas de .ϵ

Sariel Har-Peled
fonte
Obrigado. Estou certo ao pensar que, mesmo no caso de termos um limite polinomial no número de retângulos / quadrados, ainda não está claro se o problema está em P?
Raphael
1
Aqui estão meus 2 centavos de adivinhação / especulação ... Seria surpreendente se estiver em P - você precisaria mostrar algumas propriedades extras da solução ideal. No entanto, meu palpite seria que uma prova formal da dureza NP está fora de alcance - o problema tem muita estrutura. Feder e Greene mostraram que o agrupamento do centro k é NP-difícil de aproximar dentro de um determinado fator. Acho / especulam que sua prova pode ser usado para provar que o problema acima é NP-Hard se o polígono tem buracos ...
Sariel Har-Peled
2

Estes dois documentos abordam seu problema:

EG Birgin e RD Lobato, " Embalagem ortogonal de retângulos idênticos dentro de regiões convexas isotrópicas ", Computers & Industrial Engineering 59, pp. 595-602, 2010. 

EG Birgin, JM Martínez, FH Nishihara e DP Ronconi, " Embalagem ortogonal de itens retangulares dentro de regiões convexas arbitrárias por otimização não linear ", Computers & Operations Research 33, pp. 3535-3548, 2006.

 

Marcus Ritt
fonte
Estes documentos analisam a solução do problema na prática. Tanto quanto posso dizer, a pergunta é perguntar se o problema é conhecido por ser NP-difícil.
András Salamon
3
É bastante fácil mostrar que está no NP. Suponha que eu lhe forneça um diagrama da embalagem ideal que indique quais quadrados estão tocando em quais lados do polígono e quais quadrados estão acima / abaixo / esquerda / direita de outros quadrados. A questão de saber se é possível encontrar as coordenadas de um conjunto de quadrados que se agrupam exatamente dessa maneira é um programa linear e, portanto, você pode verificar se este é um diagrama para um empacotamento viável.
Peter Shor
4
Se todos os vértices do seu polígono são números inteiros (ou racionais), um resultado padrão em programas lineares diz que você não precisa de mais do que uma quantidade polinomial de precisão extra, e o programa linear pode ser resolvido exatamente em tempo polinomial. Desculpas se você já sabia disso, mas não posso dizer pelo seu comentário acima - e mesmo se você soubesse, algumas pessoas não.
Peter Shor
2
Obrigado. Eu sabia disso uma vez, mas foi bom ser lembrado. Também parece que você pode ter um número exponencial de quadrados empacotados no polígono, então não tenho certeza se você pode dar ao luxo de listar todos eles. Talvez haja alguma escala que você possa fazer para contornar isso?
Raphael
3
@ Rafael: Eu estava assumindo (sem justificativa) que você tinha um limite polinomial no número de quadrados. Se você permitir polígonos de tamanho exponencial, as coisas ficam muito mais complicadas.
Peter Shor
1

Peter Shor observou que, ao redimensionar, esse problema se torna sobre empacotar quadrados de unidades em um polígono convexo.

Editar: o restante desta resposta não se aplica, pois elimina o requisito explicitamente declarado de que as formas a serem compactadas são do mesmo tamanho.


A questão relacionada NP-Dureza de um caso especial de problema de empacotamento ortogonal menciona um artigo com o resultado necessário para a primeira pergunta:

  • Empacotando quadrados em um quadrado, Joseph YT. Leung, Tommy W. Tam, CS Wong, Gilbert H. Young e Francis YL Chin, Jornal de Computação Paralela e Distribuída 10 271–275. ( link )

Do artigo:

mostramos que o problema de empacotamento quadrado é fortemente NP-completo, reduzindo o problema de 3 partições.

Portanto, o problema é NP-difícil, mesmo no caso especial em que os retângulos a serem embalados são semelhantes ao contêiner. (Ao contrário dos autores deste artigo, não estou completamente convencido de que o problema esteja no NP, pois as posições podem precisar ser especificadas com grande precisão, o que pode fazer com que a verificação não seja mais polinomial no tamanho da entrada. )

András Salamon
fonte
5
Olhando para o papel, a partir dos diagramas, parece que os quadrados a serem embalados não são do mesmo tamanho.
precisa
1
@ Peter: Você está certo, este artigo não implica nada sobre o problema de Raphaël.
András Salamon
0

Talvez este artigo possa ser do seu interesse:

Mosaico de polígonos com retângulos de Kenyon & Kenyon no FOCS 92.

Sylvain Peyronnet
fonte
Obrigado. No entanto, se eu entendi direito, um ladrilho cobre exatamente o polígono. Isso quase nunca será possível no meu caso (considere um triângulo arbitrário com alguma orientação arbitrária) que parece tornar meu problema de otimização fundamentalmente diferente.
Raphael
na verdade, este não é o mesmo problema, meu erro.
Sylvain Peyronnet 30/03
0

Se o polígono no qual você deseja compactar não for necessariamente convexo, acho que o problema se torna difícil para NP. Aqui está uma prova muito superficial. A redução é devido a algum problema do tipo Planar-3-SAT. Para cada variável, você pode ter um lugar de 1,1 x 1, dependendo de onde nesta área você colocar um quadrado irá determinar se sua variável é verdadeira ou falsa. Além disso, se você deixar a área .1 esquerda / direita, poderá mover outros dois quadrados um pouco mais para dentro e também os que estão atrás deles, eventualmente dando outro espaço .1 livre em outro lugar que juntos agora afetem quatro quadrados e assim por diante. Depois de ter tantas cópias quanto as ocorrências dos respectivos literais, você conecta esses tubos ao componente de cláusula respectivo e, em seguida, novamente usa algum dispositivo semelhante para garantir que dos três tubos de entrada pelo menos um tenha espaço .1 extra.

domotorp
fonte
1
Isso parece plausível. Observe que Raphaël forneceu um link em um comentário maven.smith.edu/~orourke/TOPP/P56.html com um ponteiro para um artigo com a redução real.
András Salamon
Oh, eu não notei, thx.
Domotorp 20/03