En geometría, un recubrimiento o cobertura de un polígono es un conjunto de unidades básicas o primitivas (como por ejemplo, cuadrados) cuya unión es igual al polígono. Un problema de recubrimiento con polígonos consiste en encontrar la cobertura de un polígono dado con el menor número posible de unidades. Este es un tipo importante de problemas en geometría computacional.

Existen muchos problemas de cobertura de polígonos diferentes, según el tipo de polígono que se recubra. Un ejemplo de problema de cobertura de polígonos es: dado un polígono rectilineal, encontrar el conjunto más pequeño de cuadrados cuya unión sea igual al polígono.

En algunos casos, no se requiere cubrir todo el polígono, sino solo sus aristas (esto se denomina cobertura de aristas del polígono) o sus vértices (esto se denomina cobertura de vértices del polígono).

Una cobertura mínima es aquella que no contiene ninguna otra cobertura (es decir, un mínimo local).

A su vez, un mínimo de cobertura es una cobertura con el menor número de unidades posible (es decir, un mínimo global). Todo mínimo de cobertura es una cobertura mínima, pero no al revés.

Problemas relacionados En un problema de cobertura, las unidades del recubrimiento pueden superponerse, siempre que su unión sea exactamente igual al polígono objetivo. Esto contrasta con un problema de empaquetado (en el que las unidades deben ser disjuntas y su unión puede ser menor que el polígono objetivo), y con un problema de partición de un polígono (en el que las unidades deben ser disjuntas y su unión debe ser igual al polígono objetivo).

Un problema de recubrimiento de polígonos es un caso especial del problema del conjunto de cobertura. En general, el problema de encontrar el conjunto más pequeño de recubrimientos es NP-completo, pero para clases especiales de polígonos, el recubrimiento de polígonos más pequeño se puede encontrar en tiempo polinómico.

Recubrimiento de un polígono rectilíneo con cuadrados Un polígono rectilineal siempre se puede cubrir con un número finito de vértices del polígono. El algoritmo utiliza un enfoque de optimización local: construye la cobertura seleccionando iterativamente los cuadrados máximos esenciales para la cobertura (es decir, que contienen puntos no cubiertos por otros cuadrados máximos) y eliminando del polígono los puntos que se vuelven innecesarios (es decir, innecesarios para albergar futuros cuadrados). A continuación, se muestra un pseudocódigo simplificado del algoritmo:

Mientras el polígono P no esté vacío: Seleccionar un cuadrado continuador s en P. Si el vuelo de s aún no está cubierto, añadir s a la cobertura. Eliminar el vuelo de s de P. Si lo que queda de s es un continuador de un solo nudo, eliminar de P un rectángulo adyacente al nudo, dejando una distancia de seguridad suficiente para futuros cuadrados.

Para polígonos que pueden contener huecos, encontrar un mínimo de dicha cobertura es NP-difícil. Esta marcada diferencia entre polígonos sin agujeros y polígonos generales se puede explicar intuitivamente con base en la siguiente analogía entre los cuadrados máximos de un polígono rectilíneo y los nodos de un grafo no dirigido:

Algunos cuadrados máximos tienen una intersección continua con el borde del polígono; al eliminarlos, el polígono restante permanece conectado. Estos cuadrados se denominan continuadores y son análogos a los nodos hoja (nodos con una sola arista) que pueden eliminarse sin desconectar el grafo. Otros cuadrados máximos son separadores: al eliminarlos, el polígono se divide en dos polígonos inconexos. Son análogos a los nodos con dos o más aristas que, al eliminarlos, dejan un resto inconexo.

En un polígono rectilíneo sin agujeros, todos los cuadrados máximos son continuadores o separadores. Por lo tanto, dicho polígono es análogo a un árbol. Un polígono general es análogo a un grafo general. Al igual que el problema de cobertura de vértices es polinómico para grafos de árbol, pero NP-difícil para grafos generales, el problema de recubrimiento de cuadrados es lineal para polígonos sin agujeros, pero NP-difícil para polígonos generales.

Es posible usar el algoritmo lineal para obtener una aproximación 2, es decir, un recubrimiento con un máximo de cuadrados, donde "opt" es el número de cuadrados en un recubrimiento mínimo:Prof. Reuven Bar-Yehuda in personal communication

Para cada agujero, encontrar un cuadrado s que lo conecte con el límite externo. Cortar s del polígono y luego pegar dos copias superpuestas de s (véase la figura). El polígono resultante no es plano, pero sigue siendo bidimensional y ahora no tiene agujeros. Ahora, usar el algoritmo original para encontrar un recubrimiento mínimo.

El número de cuadrados en el recubrimiento resultante es como máximo , donde agujeros es el número de orificios. Es posible demostrar que . Por lo tanto, el número de cuadrados en el recubrimiento es como máximo .

Cobertura de un polígono rectilíneo con rectángulos Para polígonos rectilíneos generales, el problema de encontrar una cobertura mínima de rectángulos es NP-difícil, incluso cuando el polígono objetivo no tiene agujeros. Se han sugerido varias soluciones parciales para este problema:

En polígonos ortogonalmente convexos, el número de rectángulos en una cobertura mínima es igual al número de bloques en un antirectángulo, y este hecho puede utilizarse para construir un algoritmo de tiempo polinómico para encontrar una cobertura mínima por rectángulos. Incluso cuando el polígono objetivo es solo semiortogonalmente convexo (es decir, solo en la dirección y), se puede encontrar una cobertura mínima por rectángulos en un tiempo O("n"2), donde n es el número de vértices del polígono. Un algoritmo de aproximación que ofrece buenos resultados empíricos con datos reales se presenta en el Journal of Experimental Algorithmics. Para polígonos rectilíneos que pueden contener huecos, existe un algoritmo de aproximación de factor O().

Cobertura de un polígono rectilíneo con polígonos ortogonalmente convexos Para un polígono rectilineal convexo semiortogonalmente (es decir, solo en la dirección x), se puede encontrar una cobertura mínima de polígonos ortogonalmente convexo en tiempo O("n"^2), donde n es el número de vértices del polígono. Lo mismo ocurre con una cobertura mediante polígonos estrellados rectilíneos.

El número de componentes ortogonalmente convexos en un recubrimiento mínimo puede, en algunos casos, determinarse sin encontrar el recubrimiento mismo, en tiempo O(n).

Recubrimiento de un polígono rectilíneo con polígonos estrellados Una estrella rectilínea es un polígono P que contiene un punto p, tal que para cada punto q en P, existe un polígono ortogonalmente convexo que contiene a p y a q.

El problema de cubrir un polígono con polígonos estrellados es una variante del problema de la galería de arte.

El grafo de visibilidad para el problema de cubrir mínimamente polígonos rectilineales sin agujeros con polígonos estrellados es un grafo perfecto. Esta propiedad de perfección implica un algoritmo polinómico para encontrar un recubrimiento mínimo de cualquier polígono rectilíneo con polígonos estrellados rectilíneos.

Cubrir un polígono sin ángulos agudos con cuadrados o rectángulos La clase más general de polígonos para los que se pueden encontrar cubrimientos con cuadrados o rectángulos es la clase de polígonos sin ángulos agudos internos. Esto se debe a que un ángulo agudo no puede cubrirse con un número finito de rectángulos. Este problema es NP-difícil, pero existen varios algoritmos de aproximación., Grazyna Zwozniak, 1998

Cubrir un polígono con rectángulos de una familia finita En algunos casos, un polígono debe cubrirse no con rectángulos arbitrarios, sino con rectángulos de una familia finita.

Cubrir un polígono con triángulos Encontrar el conjunto más pequeño de triángulos que cubra un polígono dado es NP-difícil. También es difícil de aproximar: cualquier algoritmo de tiempo polinómico podría encontrar un cubrimiento con un tamaño de (1 + 1/19151) veces el cubrimiento mínimo.

Si el polígono está en posición general (es decir, no hay dos aristas colineales), entonces cada triángulo puede cubrir como máximo 3 aristas del polígono. Por lo tanto, cada triangulación de un polígono es una 3-aproximación.

Si la cobertura se limita a triángulos cuyos vértices son vértices del polígono (es decir, no se permiten puntos de Steiner), entonces el problema es NP-completo.

Si no se permiten puntos de Steiner y el polígono está en posición general (es decir, no hay dos aristas colineales), entonces toda cobertura mínima sin puntos de Steiner es también una partición mínima del polígono en triángulos (es decir, los triángulos en la cobertura mínima no se superponen). Por lo tanto, el problema de cobertura mínima es idéntico al problema de triangulación de polígonos, que puede resolverse en tiempo O(nlog n). Nótese que si se descarta el supuesto de la posición general, hay polígonos en los que los triángulos en la cobertura óptima se superponen, como por ejemplo en el caso de la estrella de David.

El problema de cubrir solo el borde de un polígono con triángulos es NP-completo, pero existe una 2-aproximación eficiente.

Cubrir un polígono con polígonos convexos

Cubrir un polígono (que puede contener huecos) con polígonos convexos es NP-difícil. También se ha demostrado que es -completo. Existe un algoritmo de aproximación O(log n).

Cubrir un polígono con polígonos convexos es NP-difícil incluso cuando el polígono objetivo carece de orificios.. También es APX-difícil, pero existe un algoritmo de aproximación de 6 para el caso sin huecos. El problema es NP-completo cuando el recubrimiento no debe introducir nuevos vértices (es decir, no se permiten puntos de Steiner).

Cubrir un polígono con polígonos estrellados

Cubrir un polígono simple con polígonos estrellados es -completo, al igual que la versión donde un punto en el núcleo de cada estrella debe estar contenido en una arista del polígono.

Cubrir un conjunto de puntos con cuadrados idénticos Dado un conjunto S de puntos en el plano y un conjunto de cuadrados idénticos, el objetivo es encontrar el menor número de cuadrados que pueda cubrir todos los puntos en S.

Supóngase que, para cada punto p en S, se coloca un cuadrado con centro en p. Sea GS el grafo de intersección de estos cuadrados. Nótese que dos puntos en S pueden cubrirse con un solo cuadrado si y solo si los dos cuadrados centrados en ellos se intersecan. Por lo tanto, cubrir los puntos en S con cuadrados equivale a un cubrimiento clique de GS. Encontrar el mínimo de cuadrados que recubren S es NP-difícil; la demostración se realiza por reducción a un problema de satisfacibilidad booleana.

Otras combinaciones Cubrir un polígono (que puede contener huecos) con polígonos espirales es NP-difícil.

También se ha estudiado la cobertura de un polígono con pseudotriángulos.

Puede encontrarse información adicional en el Handbook of Computational Geometry.

Véase también Problema de cobertura (combinatoria) Problema de la galería de arte Teselado

Referencias

Categoría:Geometría computacional Categoría:Polígonos Categoría:Problemas de recubrimiento Categoría:Problemas NP-completos