Partición de un polígono

Algunos casos especiales de partición de polígonos: una colección de polígonos divisibles en formas congruentes a sí mismas (denominadas repiteselas)

En geometría, una partición de un polígono es un conjunto de unidades primitivas (por ejemplo, cuadrados), que no se superponen y cuya unión es igual a un polígono dado. Un problema de partición poligonal consiste en encontrar una disección que sea mínima en algún sentido, como por ejemplo, una partición con el menor número de unidades o con unidades de longitud lateral total más pequeña.

La partición de polígonos es una clase importante de problemas en geometría computacional. Hay muchos problemas diferentes de partición de polígonos, según el tipo de polígono objeto de partición y de los tipos de unidades permitidas en la misma.

El término descomposición de polígonos se utiliza a menudo como un término general que incluye tanto el recubrimiento de un polígono como su partición.

Aplicaciones

La descomposición de polígonos se aplica en varias áreas:

• Las técnicas de reconocimiento de patrones extraen información de un objeto para poder describirlo, identificarlo o clasificarlo. Una estrategia establecida para reconocer un objeto poligonal general es descomponerlo en componentes más simples, luego identificar los componentes y sus interrelaciones y utilizar esta información para determinar la forma del objeto.
• En el procesamiento de datos mediante integración a muy gran escala, los diseños se representan como polígonos, y un método de preparación para la litografía por haz de electrones es descomponer estas regiones poligonales en figuras fundamentales. La descomposición de polígonos también se utiliza en el proceso de dividir la región de enrutamiento en canales.
• En geometría computacional, los algoritmos para problemas de polígonos generales suelen ser más complejos que los de tipos restringidos de polígonos, como los convexos o los de forma de estrella. El problema de un punto en un polígono es un ejemplo. Una estrategia para resolver algunos de estos tipos de problemas en polígonos generales es descomponer el polígono en componentes simples, resolver el problema en cada componente usando un algoritmo especializado y luego combinar las soluciones parciales.
• Otras aplicaciones incluyen la compresión de datos, las bases de datos, el procesamiento digital de imágenes y la computación gráfica.

Dividir un polígono en triángulos

El problema de partición de polígonos mejor estudiado es la partición en el menor número de triángulos, también llamado triangulación. Para un polígono sin agujeros y con $n$ vértices, se puede calcular una triangulación en el tiempo $\mathrm{\Theta }(n)$. Para un polígono con agujeros, existe un límite inferior de $\mathrm{\Omega }(n\log n)$.

Un problema relacionado es la partición en triángulos con una longitud total de aristas mínima, también llamada triangulación de peso mínimo.

Dividir un polígono en pseudotriángulos

Se han estudiado las mismas dos variantes del problema para el caso en el que las piezas deberían ser pseudotriángulos: polígonos que, al igual que los triángulos, tienen exactamente tres vértices convexos. Las variantes son: dividir en un número más pequeño de pseudotriángulos y dividir en pseudotriángulos con una longitud total mínima de aristas.

Dividir un polígono rectilíneo en rectángulos

Una subfamilia especial de problemas de partición de polígonos surge cuando el polígono grande es un polígono rectilineal (también llamado: polígono ortogonal). En este caso, la forma del componente más importante a considerar es el rectángulo.

Las particiones rectangulares tienen muchas aplicaciones. En el diseño de integración a muy gran escala, es necesario descomponer las máscaras en las formas más simples disponibles en los generadores de patrones litográficos, y también surgen problemas similares de descomposición de máscaras en el diseño de micromatrices de ácido desoxirribonucleico. Las particiones rectangulares pueden simplificar las operaciones de convolución en el procesamiento digital de imágenes y pueden usarse para comprimir gráficos rasterizados. Se han aplicado problemas de descomposición de matrices estrechamente relacionados con la planificación de los tratamientos de radioterapia, y también se han utilizado particiones rectangulares para diseñar secuencias de autoensamblaje robótico.

Minimizar el número de componentes

El problema de minimizar el número de rectángulos componentes es polinómico: se conocen varios algoritmos en tiempo polinómico. ConsúltesePlantilla:Rp yPlantilla:Rp para ver desarrollos al respecto.

El problema de dividir un polígono rectilíneo en el menor número de "cuadrados" (a diferencia de los rectángulos arbitrarios) es NP-difícil.

Minimizar la longitud total de las aristas

En algunas aplicaciones, es más importante minimizar la longitud total de cortes necesarios (por ejemplo, para minimizar el costo de realizar la partición o reducir la cantidad de polvo generado). Este problema se denomina partición rectangular de longitud mínima de borde. Fue estudiado por primera vez por Lingas, Pinter, Rivest y Shamir en 1982. La complejidad en tiempo de ejecución de este problema depende crucialmente de si se permite que el polígono en bruto tenga agujeros o no.

Si el polígono sin formato está libre de agujeros, entonces se puede encontrar una partición óptima en el tiempo $O(n^4)$, donde n es el número de vértices del polígono. En el caso especial de un polígono de histograma, la complejidad mejora a $O(n^3)$. El algoritmo utiliza programación dinámica y se basa en el siguiente hecho: si el polígono no tiene agujeros, entonces tiene una partición de longitud mínima en la que cada segmento de línea máximo contiene un vértice del límite. La razón es que, en cualquier partición de longitud mínima, cada segmento de línea máximo puede ser empujado hasta que llegue a uno de los vértices del límite, sin cambiar la longitud total. Por lo tanto, solo hay $O(n^2)$ candidatos para un segmento de línea en una partición óptima, y se pueden verificar de manera eficiente mediante programación dinámica.Plantilla:Rp

Si el polígono en bruto puede tener agujeros, incluso si son agujeros degenerados (es decir, puntos aislados), el problema es NP-difícil. Esto se puede demostrar mediante la reducción Planar SAT. Para el caso en el que todos los agujeros son puntos aislados, se han desarrollado varias aproximaciones de factor constante:

• Una aproximación de (3+sqrt(3)) en el tiempo $O(n^2)$.
• Una aproximación de (3+sqrt(3)) en el tiempo $O(n\log n)$.
• Una aproximación de 4 en el tiempo $O(n\log n)$ (más generalmente, en d dimensiones, es una aproximación de $2d$ en el tiempo $O(dn\log n)$).
• Una aproximación de 3 en el tiempo $O(n^4)$.
• Una aproximación de 1,75 en el tiempo $O(n^5)$ (más generalmente, en d dimensiones, es una aproximación $2d-4+4/d$ en el tiempo $O(d{n}^{2d+1})$). Esta última aproximación utiliza una variante restringida del problema llamado partición con guillotina, en el que los cortes deben ser cortes de guillotina (cortes de borde a borde).
• Varios esquema de aproximación de tiempo polinómico utilizan sofisticados cortes de guillotina.

Minimizar el número de espacios en blanco

En esta configuración, el polígono grande ya contiene algunos rectángulos separados por pares. El objetivo es encontrar una partición del polígono en rectángulos de modo que cada rectángulo original esté contenido en una de las piezas y, sujeto a esto, el número de espacios en blanco (piezas que no contienen un rectángulo original) sea tan pequeño como sea posible. Se conocen los siguientes resultados:

• Si el polígono grande es un rectángulo, entonces en cualquier disposición máxima de n rectángulos, todos los agujeros son rectángulos y su número es como máximo $n-\lceil 2\sqrt{n}-1\rceil$, lo que se trata de una solución ajustada.
• Si el polígono grande es un polígono rectilíneo con T vértices especulares, entonces en cualquier disposición máxima de n rectángulos, los agujeros se pueden dividir en como máximo $T+n-\lceil 2\sqrt{n}-1\rceil$ rectángulos, lo que también se trata de una solución ajustada.

Dividir un polígono en trapecios

En los sistemas de procesamiento de imágenes a VLSI, a menudo es necesario dividir una región poligonal en el número mínimo de trapecios, con dos lados horizontales. Un triángulo de lado horizontal se considera un trapezoide de dos lados horizontales, uno de los cuales es degenerado. Para un polígono sin agujeros con $n$ lados, se puede encontrar una partición más pequeña en el tiempo $O(n^2)$.

Si el número de trapecios no tiene por qué ser mínimo, se puede encontrar una solución trapezoidal en el tiempo $O(n)$, como subproducto de un algoritmo de triangulación de un polígono.

Si el polígono contiene agujeros, el problema es NP-completo, pero se puede encontrar una aproximación de 3 en el tiempo $O(n\log n)$.

Dividir un polígono en cuadriláteros convexos

Una cuadrilateralización o una cuadrangulación es una partición en cuadriláteros.

Una característica recurrente de los problemas de cuadrangulación es si se permiten puntos de Steiner, es decir, si el algoritmo puede sumar puntos que no sean vértices del polígono. Permitir puntos de Steiner puede permitir divisiones más pequeñas, pero entonces es mucho más difícil garantizar que las divisiones encontradas por un algoritmo tengan un tamaño mínimo.

Existen algoritmos de tiempo lineal para cuadrangulaciones de polígonos sin agujeros con puntos de Steiner, pero no se garantiza que encuentren una partición más pequeña.

Dividir un polígono en m-gonos

Una generalización de los problemas anteriores es la partición en polígonos que tienen exactamente m lados, o como máximo m lados. Aquí el objetivo es minimizar la longitud total de los bordes. Este problema se puede resolver en tiempo polinómico en n y m.

Dividir un polígono en polígonos convexos

Al dividir un polígono general en polígonos convexos se han estudiado varios objetivos.

Minimizar el número de componentes

El problema de partición convexa óptimo es dividir un polígono no convexo en la menor cantidad posible de polígonos convexos, utilizando solo los vértices del polígono inicial. Existen algoritmos exactos y aproximados para este problema.

Minimizar el número de espacios en blanco

El polígono original ya contiene algunas figuras convexas disjuntas por pares, y el objetivo es dividirlo en polígonos convexos de manera que cada figura original esté contenida en una de las piezas, y sujeto a esto, el número de espacios en blanco (piezas que no contienen la figura original) sea lo más pequeño posible. Si el polígono grande es convexo, entonces en cualquier disposición máxima de n figuras convexas, todos los agujeros son convexos y su número es como máximo $2n-5$, lo que se trata de una solución ajustada.

Igualar el área y el perímetro

El problema de "partición justa de polígonos" consiste en dividir un polígono (convexo) en piezas (convexas) con un perímetro igual y un área igual (este es un caso especial del corte de pastel justo). Cualquier polígono convexo se puede cortar fácilmente en cualquier número n de piezas convexas con un área de exactamente 1/n. Sin embargo, garantizar que las piezas tengan igual área y perímetro igual es más difícil. Existen algoritmos para resolver este problema cuando el número de piezas es una potencia de 2.

Una generalización de este problema es cuando las medidas de área y perímetro se reemplazan con una medida en el cuerpo y en el límite del polígono, respectivamente. Este problema fue estudiado para 2 y 3 piezas.

Existe una generalización adicional para manejar cualquier número de medidas.

Formas de componentes más generales

Se han estudiado formas más generales de piezas, entre ellas: formas espirales, en estrella y polígonos monótonos. Consúltese el trabajo de J. Mark Keil para ver desarrollos al respecto.

Véase también

• Recubrimiento de un polígono – un problema relacionado en el que se permite que las piezas se superpongan.
• Problema de empaquetado – un problema relacionado en el que las piezas tienen que caber dentro de todo el objeto grande pero no tienen que cubrirlo por completo.
• Teselado regular – un problema de dividir todo el plano en polígonos simples como rectángulos.
• Cuadratura del cuadrado – un problema de dividir un cuadrado de lados de longitud entera mediante cuadrados distintos también de lados de longitud entera.
• Particionado del espacio
• Rompecabezas de teselado: un rompecabezas que consiste en empaquetar varias piezas determinadas en un polígono más grande determinado.
• Partición con guillotina