Exact and Approximation Algorithms for Computing Optimal Fat Decompositions.
The minimum α-fat decomposition problem is the problem of decomposing a simple polygon into fewest subpolygons, each with aspect ratio at most α, for a given α > 0. The main result in the paper is a polynomial time algorithm that solves the version of this problem that disallows Steiner points. The algorithm returns an optimal α-fat decomposition, if there is one, and reports failure otherwise. We also devise a faster approximation algorithm that produces, for any ε > 0, an (α + ε)-fat decomposition with as few polygons as an optimal α-fat decomposition.
| Main Author: | Damian, Mirela. |
|---|---|
| Format: | |
| Language: | English |
| Published: |
2004
|
| Online Access: |
http://ezproxy.villanova.edu/login?url=https://digital.library.villanova.edu/Item/vudl:175674 |