Particionar una forma conectada en rectángulos

8

Me imagino que esta debe ser una pregunta introductoria de geometría computacional, pero no estoy seguro de las mejores frases de búsqueda, y también estoy interesado en las variaciones de la pregunta, por lo que espero punteros a referencias útiles. Estoy interesado en algoritmos factibles para el siguiente problema.

Entrada: A conectados conjunto de puntos (de forma) en . Salida: una partición de la forma en rectángulos, de modo que los rectángulos no se superpongan entre sí y cubran solo la forma, no el espacio "vacío".Z×Z

Estoy interesado en encontrar el número mínimo de rectángulos, el "mejor" conjunto de rectángulos para cualquier noción de mejor, si este problema se vuelve más fácil o más difícil para diferentes clases de formas.

Gracias. :-)

reference-request cg.comp-geom Aaron Sterling
fuente
3
Mire esta pregunta de MathOverflow
Peter Shor
@ Peter Shor: Muchas gracias. Eso se ve exactamente como lo que necesito.
Aaron Sterling el
3
Entonces, ¿debería ser esta una respuesta? ¿o debería cerrarse la pregunta?
Suresh Venkat
44
@Suresh: Creo que resuelve mi pregunta, aunque quizás alguien más podría tener algo que agregar sobre las variantes del problema. Preferiría que la pregunta permanezca abierta en caso de que alguien más tenga algo que agregar. Me complacería aceptarlo como respuesta si @Peter Shor lo publicó como tal.
Aaron Sterling
Supongo que puedo publicarlo como respuesta, aunque parece que hice muy poco trabajo. Debe esperar para aceptarlo hasta que esté seguro de que nadie más tiene nada que agregar.
Peter Shor

Respuestas:

9

David Eppstein dio una excelente respuesta a esta pregunta aquí en MathOverflow (respondiendo a una pregunta para la que no es una respuesta tan buena). Para resumir, hay un algoritmo de tiempo polinómico para encontrar el número mínimo de rectángulos.

Peter Shor
fuente