Peeling Rotten Potatoes for a Faster Approximation of Convex Cover
Abstract
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\).
Fields of Study & Subjects
Computational Geometry and Mesh Generation
Complexity and Algorithms in Graphs
Facility Location and Emergency Management
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 2633–2643
- Publication date
- 1 January 2026
- Language
- EN