Potatisskalning

Den här artikeln handlar om ett problem inom beräkningsgeometri. För enheterna som används för att skala potatis, se skalare .

I beräkningsgeometri är problemet med potatisskalning eller konvex skalle ett problem med att hitta den konvexa polygonen av största möjliga område som ligger inom en given icke-konvex polygon . Det poserades oberoende av Goodman och Woo och löstes i polynomtid av Chang och Yap. Exponenten för polynomets tidsgräns är hög, men samma problem kan också ungefärligt approximeras i nästan linjär tid.