Constant-Factor Approximation Algorithms for Convex Cover and Hidden Set in a Simple Polygon

Given a simple polygon P , the minimum convex cover problem seeks to cover P with the fewest convex polygons that lie within P . The maximum hidden set problem seeks to place within P a maximum cardinality set of points no two of which see each other. We give constant factor approximation algorithms for both problems. Previously, the best approximation factor for the minimum convex cover was logarithmic; for the maximum hidden set problem, no approximation algorithm was known.