Minimum Star Partitions of Simple Polygons in Polynomial Time

We devise a polynomial-time algorithm for partitioning a simple polygon P into a minimum number of star-shaped polygons. The question of whether such an algorithm exists has been open for more than four decades Avis and Toussaint, Pattern Recognit., 1981 and it has been repeated frequently, for example in O'Rourke's famous book Art Gallery Theorems and Algorithms, 1987. In addition to its strong theoretical motivation, the problem is also motivated by practical domains such as CNC pocket milling, motion planning, and shape parameterization. The only previously known algorithm for a non-trivial special case is for P being both monotone and rectilinear Liu and Ntafos, Algorithmica, 1991. For general polygons, an algorithm was only known for the restricted version in which Steiner points are disallowed Keil, SIAM J. Comput., 1985, meaning that each corner of a piece in the partition must also be a corner of P. Interestingly, the solution size for the restricted version may be linear for instances where the unrestricted solution has constant size. The covering variant in which the pieces are star-shaped but allowed to overlap - known as the Art Gallery Problem - was recently shown to be ∃ℝ-complete and is thus likely not in NP Abrahamsen, Adamaszek and Miltzow, STOC 2018 this is in stark contrast to our result. Arguably the most related work to ours is the polynomial-time algorithm to partition a simple polygon into a minimum number of convex pieces by Chazelle and Dobkin [STOC, 1979 & Comp. Geom., 1985.