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.
