Summary: The problem MINIMUM CONVEX COVER of covering a given polygon with a minimum number of (possibly overlapping) convex polygons is known to be NP-hard, even for polygons without holes [(*) J. C. Culberson and R. A. Reckhow, J. Algorithms 17, 2–44 (1994; Zbl 0811.68089)]. We propose a polynomial-time approximation algorithm for this problem for polygons with or without holes that achieves an approximation ratio of \(O(\log n)\), where n is the number of vertices in the input polygon. To obtain this result, we first show that an optimum solution of a restricted version of this problem, where the vertices of the convex polygons may lie only on a certain grid, contains at most three times as many convex polygons as the optimum solution of the unrestricted problem. As a second step, we use dynamic programming to obtain a convex polygon which is maximum with respect to the number of “basic triangles” that are not yet covered by another convex polygon. We obtain a solution that is at most a logarithmic factor off the optimum by iteratively applying our dynamic programming algorithm. Furthermore, we show that MINIMUM CONVEX COVER is APX-hard; i.e., there exists a constant \(\delta >0\) such that no polynomial-time algorithm can achieve an approximation ratio of \(1+\delta\). We obtain this result by analyzing and slightly modifying an already existing reduction (*).