Polígono dentro del problema de generalización poligonal

Me gustaría disculparme por todas las publicaciones a continuación. Elegí el foro equivocado para publicar esto originalmente. Sin embargo, en lugar de hacer de esto un desperdicio completo, he reelaborado la pregunta para que sea un verdadero problema de "Ciencia de la Computación Teórica".

Problema: cree un algoritmo que tome un conjunto de n puntos ordenados en un plano 2D que forme el contorno de un polígono A simple que puede ser cóncavo o no y cree un nuevo polígono B con m puntos de manera que:

1. todos los puntos en A están contenidos dentro de B
2. 3 <= m <n
3. B es el polígono en el conjunto de todos los B con el área más pequeña
4. B debe ser un polígono simple (es decir, sin intersecciones propias).
5. La entrada al algoritmo es el polígono A y "m".
6. Se permite la coincidencia de segmentos en B con segmentos en A.

Algunos ejemplos de entradas y salidas esperadas:

1. Si A es un cuadrado ym es 3, entonces B sería el triángulo con el área de superficie más pequeña que contiene A.
2. Si A es un hexágono ym es 4, entonces B sería un cuadrilátero con el área de superficie más pequeña que contiene A.

Buena suerte a todos los que prueben este problema. Puedo prometerle que esto será muy difícil, especialmente ahora que la solución debe ser óptima.

No sé cómo se ven sus polígonos, pero tal vez una versión simplificada del algoritmo Ramer-Douglas-Peucker sea ​​suficiente:

• para cada parte convexa , calcule el área de los triángulos formado por tres puntos consecutivos;P i P i + 1 P i + $A_j$$P_i P_{i+1} P_{i+2}$
• para cada parte cóncava , calcule el área de los dos triángulos y formado por la extensión de los dos puntos y el punto medioP i P ′ i P i + 1 P i + 1 P ′ i + 2 P i + 2 P i , P i + 2 P i + $B_k$$P_i P'_i P_{i+1}$$P_{i+1} P'_{i+2} P_{i+2}$$P_i, P_{i+2}$$P_{i+1}$
• calcule el y elimine el punto correspondiente (y los puntos de desplazamiento si la operación se realiza en la parte cóncava);$min\{A_j,B_k\}$
• bucle hasta que se hayan eliminado los puntos .$n-m$

El borde del polígono ( triángulos verdes , triángulos rojos ). A la derecha, el borde después de la eliminación de dos puntos.B $A_j$$B_k$

Para algoritmos más complejos, puede buscar " técnicas de generalización de polígonos " aunque su primera condición (los puntos en A están contenidos en B) implica algunas operaciones de escalado adicionales.

Hace mucho tiempo escribí un artículo que detallaba un algoritmo de tiempo lineal para encontrar el triángulo de área más pequeño que encierra un conjunto de puntos (o un polígono):

J. O'Rourke, Alok Aggarwal, Sanjeev Maddila, Michael Baldwin, "Un algoritmo óptimo para encontrar triángulos envolventes mínimos", J. Algorithms , 1986, 7 : 258--269. Enlace .

Nuestro trabajo fue seguido por un algoritmo general:

"Área mínima que circunscribe los polígonos", Alok Aggarwal, JS Chang y Chee K. Yap, The Visual Computer , Volumen 1, Número 2 (1985), 112-117. Enlace .

Puede usar Google Scholar para rastrear esos documentos posteriores que los citan para encontrar mejoras y trabajos relacionados.