Peeling Rotten Potatoes for a Faster Approximation of Convex Cover
For computational geometry researchers, this work provides a practical speedup for a known hard problem, though the approximation ratio remains unchanged.
The paper presents a faster algorithm for the minimum convex cover problem, achieving an O(log n)-approximation in significantly reduced time compared to the previous O(n^{29} log n) algorithm, by discretizing the problem and solving a variant of the potato peeling problem via maximum weighted paths in DAGs.
The minimum convex cover problem seeks to cover a polygon $P$ with the fewest convex polygons that lie within $P$. This problem is $\exists\mathbb R$-complete, and the best previously known algorithm, due to Eidenbenz and Widmayer (2001), achieves an $O(\log n)$-approximation in $O(n^{29} \log n)$ time, where $n$ is the complexity of $P$. In this work we present a novel approach that preserves the $O(\log n)$ approximation guarantee while significantly reducing the running time. By discretizing the problem and formulating it as a set cover problem, we focus on efficiently finding a convex polygon that covers the largest number of uncovered regions, in each iteration of the greedy algorithm. This core subproblem, which we call the rotten potato peeling problem, is a variant of the classic potato peeling problem. We solve it by finding maximum weighted paths in Directed Acyclic Graphs (DAGs) that correspond to visibility polygons, with the DAG construction carefully constrained to manage complexity. Our approach yields a substantial improvement in the overall running time and introduces techniques that may be of independent interest for other geometric covering problems.