En geometría computacional , el problema del pelado de patatas o del cráneo convexo es un problema de encontrar el polígono convexo del área más grande posible que se encuentra dentro de un polígono simple no convexo dado . Goodman y Woo lo plantearon de forma independiente, [1] [2] y Chang y Yap lo resolvieron en tiempo polinomial . [3] El exponente del límite de tiempo polinómico es alto, pero el mismo problema también se puede aproximar con precisión en un tiempo casi lineal. [4] [5]
Referencias
- ^ Goodman, Jacob E. (1981), "Sobre el polígono convexo más grande contenido en un n -gon no convexo, o cómo pelar una papa", Geometriae Dedicata , 11 (1): 99–106, doi :10.1007/BF00183192, SEÑOR 0608164, S2CID 121212273
- ^ Woo, T. (1983), El problema del cráneo convexo, citado por Chang y Yap (1986)
- ^ Chang, JS; Sí, C.-K. (1986), "Una solución polinómica para el problema del pelado de patatas", Geometría computacional y discreta , 1 (2): 155–182, doi : 10.1007/BF02187692 , MR 0834056
- ^ Hall-Holt, Olaf; Katz, Mateo J.; Kumar, Piyush; Mitchell, Joseph SB ; Sityon, Arik (2006), "Encontrar palos grandes y patatas en polígonos", Actas del decimoséptimo simposio anual ACM-SIAM sobre algoritmos discretos , Nueva York: ACM, págs. 474–483, CiteSeerX 10.1.1.59.6770 , doi : 10.1145/1109557.1109610, ISBN 978-0898716054, SEÑOR 2368844, S2CID 7212084
- ^ Cabello, Sergio; Cibulka, Josef; Kynčl, Jan; Saumell, María; Valtr, Pavel (2017), "Pelar patatas de forma casi óptima en un tiempo casi lineal", SIAM Journal on Computing , 46 (5): 1574–1602, arXiv : 1406.1368 , doi : 10.1137/16M1079695, MR 3708542
