Particionando uma forma conectada em retângulos

8

Imagino que seja uma pergunta introdutória de geometria computacional, mas não tenho certeza das melhores frases de pesquisa e também estou interessado em variações da pergunta, por isso espero encontrar indicadores úteis para referências. Estou interessado em algoritmos viáveis ​​para o seguinte problema.

Entrada: A conectado conjunto de pontos (forma) em . Saída: uma partição da forma em retângulos, de modo que os retângulos não se sobreponham e cubram apenas a forma, sem espaço "vazio".Z×Z

Estou interessado em encontrar o número mínimo de retângulos, o "melhor" conjunto de retângulos para qualquer noção de melhor, se esse problema se torna mais fácil ou mais difícil para diferentes classes de formas.

Obrigado. :-)

reference-request cg.comp-geom Aaron Sterling
fonte
3
Veja esta questão do MathOverflow
Peter Shor
@ Peter Shor: Muito obrigado. Parece exatamente o que eu preciso.
Aaron Sterling
3
Então isso deveria ser uma resposta? ou a pergunta deve ser encerrada?
Suresh Venkat
4
@ Suresh: Eu acho que resolve minha pergunta, embora talvez alguém possa ter algo a acrescentar sobre variantes do problema. Eu preferiria que a pergunta permanecesse em aberto caso alguém mais tivesse algo a acrescentar. Eu ficaria feliz em aceitá-lo como resposta se @Peter Shor publicou como tal.
Aaron Sterling
Acho que posso postá-lo como resposta, mesmo que pareça que eu fiz muito pouco trabalho. Você deve esperar para aceitá-lo até ter certeza de que mais ninguém tem mais nada a acrescentar.
quer

Respostas:

9

David Eppstein deu uma excelente resposta para esta pergunta aqui no MathOverflow (respondendo a uma pergunta para a qual não é uma resposta tão boa). Para resumir, existe um algoritmo de tempo polinomial para encontrar o número mínimo de retângulos.

Peter Shor
fonte