Exact and approximation algorithms for computing optimal fat decompositions (Q598551): Difference between revisions

The author studies the minimum \(\alpha\)-fat decomposition problem, that is the problem of decomposing a simple polygon into fewest subpolygons, each with aspect ratio \(\alpha\), for a given \(\alpha > 0\). His main result is a polynomial type algorithm that solves the version of this problem that disallows Steiner points. The algorithm returns an optimal \(\alpha\)-fat decomposition, if there is one, otherwise reports failure [cf. \textit{M. van Kreveld}, Comput. Geom. 9, No. 4, 197--210 (1998; Zbl 0894.68155)]. The author also mentions some open problems like (i) Computation of optimal \(\alpha\)-fat decomposition problems that allow Steiner points; (ii) Computation of a minimum \(\alpha\)-fat covering of a simple polygon for a given constant \(\alpha > 0\).