Número mínimo de rectángulos que cubren un conjunto de cuadrados de lado unidad

Question

Supongamos que tengo un número arbitrario de los adyacentes 1x1 casillas en una cuadrícula (Adyacente define como "cada cuadrado comparte al menos un lado con el otro"). Estoy buscando una buena manera de encontrar el número mínimo de (posiblemente se superponen) los rectángulos que se cubren todas las plazas exactamente. Esto es, la unión de todos los rectángulos tiene exactamente la misma forma y tamaño que la unión de todos los cuadrados.

Por ejemplo, la L tetromino puede ser cubierto con dos rectángulos (3x1;2x1, 2x1;2x1 o 3x1;1x1).

En mi ejemplo del problema necesito encontrar un arreglo específico de los rectángulos para que yo pueda comprobar si un punto está dentro de la forma. Lo que realmente estoy buscando es un algoritmo que de manera eficiente (tiempo polinomio) encuentra una cubierta en la que el número de rectángulos es menor que 2n (siendo n el óptimo cubrimiento).

Answer 1

He aquí un $16$-aproximación, suponiendo que el objeto no tiene agujeros. En particular, esta aproximación da distintos rectángulos, y por lo tanto, es una instancia de un Polígono que Cubre (no obstante los límites).

La unión de las plazas puede ser, alternativamente visto como una rectilíneo polígono. Nos vamos a los vértices del polígono ser el fuerte de los puntos en el límite de la poligonal. Deje $V$ el número de vértices. Voy a describir un enfoque basado en el barrido de la línea de algoritmo de triangulación. Básicamente, voy a dar un trivial triangulación si el polígono es monotono, y posteriormente se describe cómo transformar el polígono en la monotonía de las piezas.

Si el polígono es monotono y no tiene agujeros

En primer lugar, vamos a considerar lo que sucede si el polígono es monótona (en $y$ coordenadas) y que no tengan agujeros. Deje $P$ ser el número óptimo de rectángulos para cubrir este polígono. En primer lugar, yo reclamo que

$$4P \le V$$

Es decir, $V$ es en la mayoría de las $4$ multiplicado por el número de rectángulos en la respuesta óptima. Para ver esto, considere la posibilidad de cualquier rectángulo que abarca el objeto. ¿Cuál es el número máximo de vértices de este rectángulo puede tocar? La respuesta es $4$ y por lo tanto, el límite de la siguiente manera.

Ahora, podemos construir $V$ rectángulos que abarcan todo, de la siguiente manera: Vamos a $Y$ ser la lista ordenada de los distintos $y$ coordenadas de los vértices del polígono. Para cada par adyacente $y_i \in Y, y_{i+1} \in Y$, construir un rectángulo para cubrir el polígono. Claramente esto construcciones en la mayoría de las $V$ rectángulos.

Haciendo el polígono monotono

Hacemos un enfoque similar con la triangulación: hacemos el polígono monotono y cubrir cada monotono pieza por rectángulos. Podemos hacer monotonizing en un enfoque similar como en la triangulación (aludido en la wiki): cada vez que nos encontramos con un cóncavo punto de que "hacia abajo", se dibuja una línea desde el punto de la izquierda y la derecha hasta que llegamos a los límites del polígono, y cortar el polígono, la creación de polígonos separados en el proceso (lo que realmente es similar a la del algoritmo descrito en la wiki, pero en lugar de conectar con el vértice en la izquierda/derecha de los lados del polígono, creamos un nuevo vértice en el correspondiente límite). Así, cada "cóncavo" punto de crear en la mayoría de las $2$ nuevos vértices, y el $12$-aproximación de la siguiente manera.

Ahora, ¿cuántos cóncava puntos de una rectilíneo polígono? Que es en la mayoría el número de convexa de los puntos que se tienen (de hecho, es exactamente $4$ más que eso). Ahora, si $V_x$ es el número de convexa de los vértices del polígono, utilizando un razonamiento similar como antes, tenemos $4P \le V_x$, y por lo tanto, esta es una $4 \times (1+3) = 16$-aprox algoritmo.

¿Qué pasa si el polígono tiene agujeros?

Los límites en la respuesta óptima ya no se sostiene, y por lo tanto, no hay garantía de que está presente incluso si fuéramos a monotonize el polígono utilizando los vértices de los agujeros.