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...

Full description

Bibliographic Details
Main Author: Damian, Mirela.
Format: Villanova Faculty Authorship
Language:English
Published: 2004
Online Access:http://ezproxy.villanova.edu/login?url=https://digital.library.villanova.edu/Item/vudl:175674