Theory Seminar Series: Hanwen Zhang, "Minimum Star Partitions of Simple Polygones in Polynomial Time."

Abstract: We devise a polynomial-time algorithm for partitioning a simple polygon into minimum number of star-shaped polygons. The covering version in which the pieces are star-shaped but allowed to overlap--known as the Art Gallery Problem--was shown to be ∃ℝ-complete and is thus likely not in NP [Abrahamsen, Adamaszek and Miltzow, STOC 2018 & J. ACM 2022]. 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]. 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. The key step in this work is to discretize the solution space, which might be able to generalize to other minimum partitioning problems. 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].

Bio: Hanwen Zhang is a PhD fellow in the Department of Computer Science, Algorithms and Complexity at the University of Copenhagen