Partitioning a Polygon Into Small Pieces

We study the problem of partitioning a given simple polygon P into a minimum number of connected polygonal pieces, each of bounded size. We describe a general technique for constructing such partitions that works for several notions of ‘bounded size,’ namely that each piece must be contained in an axis-aligned or arbitrarily rotated unit square or a unit disk, or that each piece has bounded perimeter, straight-line diameter or geodesic diameter. The problems are motivated by practical settings in manufacturing, finite element analysis, collision detection, vehicle routing, shipping and laser capture microdissection.