Partición de un polígono

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 al 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 la partición.​

Aplicaciones

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

• Las técnicas 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 de obras de arte de 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 point-in-polygon problem 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 compresión de datos, base de datos, procesamiento digital de imágenes y 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 triangulation. Para un polígono sin agujeros con vértices $n$, se puede calcular una triangulación en el tiempo $\Theta (n)$. Para un polígono con agujeros, existe un límite inferior de $\Omega (n\log n)$.

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

Dividir un polígono en pseudotriángulos

Se estudiaron las mismas dos variantes del problema para el caso en el que las piezas deberían ser pseudotriángulo: 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 borde.

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 rectángulo.​

Las particiones rectangulares tienen muchas aplicaciones. En el diseño 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 microarrays Ácido desoxirribonucleico. Las particiones rectangulares pueden simplificar las operaciones convolución en procesamiento digital de imágenes y pueden usarse para comprimir gráfico rasterizado. Se han aplicado problemas de descomposición de matrices estrechamente relacionados a la planificación radioterapia, y también se han utilizado particiones rectangulares para diseñar secuencias de robots autoensamblaje.​

Minimizar el número de componentes

El problema de minimizar el número de rectángulos componentes es polinómico: se conocen varios algoritmos de tiempo polinomial. Consulte​ y​ para ver encuestas.

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-hard.​

Minimizar la longitud total del borde

En algunas aplicaciones, es más importante minimizar la longitud total de los cortes (por ejemplo, para minimizar el costo de realizar la partición o minimizar la cantidad de polvo). 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.

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 candidatos $O(n^{2})$ para un segmento de línea en una partición óptima, y t

Se pueden verificar de manera eficiente mediante programación dinámica.​

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

• Una aproximación (3+sqrt(3)) en el tiempo $O(n^{2})$;​
• Una aproximación (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 dimensiones d, es una aproximación $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 dimensiones d, es una aproximación $2d-4+4/d$ en el tiempo $O(dn^{2d+1})$);​ esta última aproximación utiliza una variante restringida del problema llamado guillotine partitioning, 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 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$, y esto es ajustado.
• Si el polígono grande es un polígono rectilíneo con vértices reflejos T, entonces en cualquier disposición máxima de n rectángulos, los agujeros se pueden dividir en como máximo rectángulos $T+n-\lceil 2{\sqrt {n}}-1\rceil$, y esto es ajustado.

Dividir un polígono en trapecios

En los sistemas de procesamiento de ilustraciones VLSI, a menudo es necesario dividir una región poligonal en el número mínimo de trapecio (geometría), 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 lados $n$, 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 trapezoidal en el tiempo $O(n)$, como subproducto de un algoritmo triangulación de un polígono.​

Si el polígono contiene agujeros, el problema es NP-completo, pero se puede encontrar una aproximación 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átero.

Una característica recurrente de los problemas de cuadrangulación es si se permiten Steiner point, es decir, si el algoritmo puede sumar puntos que no sean vértices del polígono. Permitir puntos 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 Steiner, pero no se garantiza que encuentren una partición más pequeña.​​

Dividir un polígono en m-gons

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 del borde. 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ígono convexo, 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 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$, y esto es ajustado.​

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 de fair cake-cutting). 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 desafiante. 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 espiral, estrella (figura geométrica) y polígono monótono. Consulte​ para ver una encuesta.

Véase también

• Polygon covering – un problema relacionado en el que se permite que las piezas se superpongan.
• Packing problem – 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 rectangles.
• Cuadratura del cuadrado – un problema de dividir un cuadrado integral usando solo otros cuadrados integrales.
• Particionado del espacio
• Tiling puzzle: un rompecabezas que consiste en empaquetar varias piezas determinadas en un polígono más grande determinado.
• Guillotine partition

Referencias

• Datos: Q25304242