Anar al contingut

Recobriment de polígons

De L'Enciclopèdia, la wikipedia en valencià
Recobriment d'un polígon per mig de triànguls

En geometria, un recobriment o cobertura d'un polígon és un conjunt d'unitats bàsiques o primitives (com per eixemple, quadrats) que la seua unió és igual al polígon. Un problema de recobriment en polígons consistix en trobar la cobertura d'un polígon donat en el menor número possible d'unitats. Est és un tipo important de problemes en geometria computacional.

Existixen molts problemes de cobertura de polígons diferents, segons el tipo de polígon que es recobrixca. Un eixemple de problema de cobertura de polígons és: donat un polígon rectilineal, trobar el conjunt més chicotet de quadrats l'unió dels quals siga igual al polígon.

En alguns casos, no es requerix cobrir tot el polígon, sino solament les seues arestes (açò es denomina cobertura d'arestes del polígon) o els seus vèrtiços (açò es denomina cobertura de vèrtiços del polígon).

Una cobertura mínima és aquella que no conté cap atra cobertura (és dir, un mínim local).

A la seua volta, un mínim de cobertura és una cobertura en el menor número d'unitats possible (és dir, un mínim global). Tot mínim de cobertura és una cobertura mínima, pero no al revés.

Problemes relacionats

En un problema de cobertura, les unitats del recobriment poden superpondre's, sempre que la seua unió siga exactament igual al polígon objectiu. Açò contrasta en un problema d'empaquetat (en el que les unitats deuen ser disjuntas i la seua unió pot ser menor que el polígon objectiu), i en un problema de partició d'un polígon (en el que les unitats deuen ser disjuntas i la seua unió deu ser igual al polígon objectiu).

Un problema de recobriment de polígons és un cas especial del problema del conjunt de cobertura. En general, el problema de trobar el conjunt més chicotet de recobriment és NP-complet, pero per a classes especials de polígons, el recobriment de polígons més chicotet es pot trobar en temps polinòmic.

Recobriment d'un polígon rectilíneo en quadrats

Un polígon rectilineal sempre es pot cobrir en un número finit de vèrtiços del polígon.[1] L'algoritme utilisa un enfocament d'optimisació local: construïx la cobertura seleccionant iterativamente els quadrats màxims essencials per a la cobertura (és dir, que contenen punts no coberts per atres quadrats màxims) i eliminant del polígon els punts que es tornen innecessaris (és dir, innecessaris per a albergar futurs quadrats). A continuació, es mostra un pseudocódigo simplificat de l'algoritme:

  • Mentres el polígon P no estiga buit:
    • Seleccionar un quadrat continuador s en P.
    • Si el vol de s encara no està cobert, afegir s a la cobertura.
    • Eliminar el vol de s de P.
    • Si lo que queda de s és un continuador d'un sol nuc, eliminar de P un rectàngul adjacent al nuc, deixant una distància de seguritat suficient per a futurs quadrats.
Procediment per a assimilar un polígon en un forat a un polígon sense forats, superponent dos còpies ("inclinades" en el dibuix, una cap a dalt i una atra cap a avall) d'una peça necessària per a conectar el forat intern en l'exterior (marcada en color vert clar)


Per a polígons que poden contindre buits, trobar un mínim de dita cobertura és NP-difícil.[2] Esta marcada diferència entre polígons sense forats i polígons generals es pot explicar intuitivamente en base en la següent analogia entre els quadrats màxims d'un polígon rectilíneo i els nodos d'un grafo no dirigit:[1]

  • Alguns quadrats màxims tenen una intersecció contínua en la vora del polígon; en eliminar-los, el polígon restant permaneix conectat. Estos quadrats es denominen continuadores i són anàlecs als nodos full (nodos en una sola aresta) que poden eliminar-se sense desconectar el grafo.
  • Atres quadrats màxims són separadores: en eliminar-los, el polígon es dividix en dos polígons inconexos. Són anàlecs als nodos en dos o més arestes que, en eliminar-los, deixen un restant inconexo.

En un polígon rectilíneo sense forats, tots els quadrats màxims són continuadores o separadores. Per lo tant, dit polígon és anàlec a un arbre. Un polígon general és anàlec a un grafo general. De la mateixa manera que el problema de cobertura de vèrtiços és polinòmic per a grafos d'arbre, pero NP-difícil per a grafos generals, el problema de recobriment de quadrats és llineal per a polígons sense forats, pero NP-difícil per a polígons generals.

És possible usar l'algoritme llineal per a obtindre una aproximació 2, és dir, un recobriment en un màxim de 2 opt quadrats, a on "opt" és el número de quadrats en un recobriment mínim:[3]

  • Per a cada forat, trobar un quadrat s que ho conecte en el llímit extern.
  • Tallar s del polígon i després pegar dos còpies superpostes de s (vore la figura). El polígon resultant no és pla, pero seguix sent bidimensional i ara no té forats.
  • Ara, usar l'algoritme original per a trobar un recobriment mínim.

El número de quadrats en el recobriment resultant és com a màxim opt + forats, a on forats és el número d'orificis. És possible demostrar que opt ≥ forats. Per lo tant, el número de quadrats en el recobriment és com a màxim 2 opt.

Vore també

Referències

  1. ↑ 1,0 1,1 Bar-Yehuda, R.; Ben-Hanoch, E.(1996).«A Linear-Clave Algorithm for Covering Simple Polygons with Similar Rectangles».International Journal of Computational Geometry & Applications.06: 79–102.doi:10.1142/S021819599600006X.
  2. ↑ Aupperle, L.J.; Conn, H.E.; Keil, J.M.; O'Rourke, Joseph(1988).«Covering orthogonal polygons with squares».Proc. 26th Allerton Conf. Commun. Control Comput..: 97–106.
  3. ↑ Prof. Reuven Bar-Yehuda in personal communication


Referències