Öresundsbron

Welcome to a seminar with Mikkel Vind Abrahamsen, Associate Professor at the Department of Computer Science at University of Copenhagen.

Title

Partitioning a Polygon into Small Pieces and Related Problems

Abstract

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. We develop constant-factor approximation algorithms, which means that the number of pieces in the produced partition is at most a constant factor larger than the cardinality of an optimal partition.

We outline a proof that the version where each piece should be contained in an axis-aligned unit square is NP-hard. A similar proof shows that the problem of packing unit squares into a simple polygon is also NP-hard. For polygons with holes, this problem had been known to be NP-hard since the early 80s, but for simple polygons, it had been conjectured to be in P.

Contact