Particionando uma forma conectada em retângulos
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×ZZ×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.
Veja esta questão do MathOverflow
@ Peter Shor: Muito obrigado. Parece exatamente o que eu preciso.
Então isso deveria ser uma resposta? ou a pergunta deve ser encerrada?
@ 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.
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.
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.