An Overview of Minimum Convex Cover and Maximum Hidden Set
For computational geometry researchers, this paper clarifies the relationship between two fundamental polygon parameters, but the results are incremental.
This paper reviews the minimum convex cover and maximum hidden set problems, proves NP-hardness of determining whether a polygon has equal convex cover and hidden set numbers, and provides examples where they differ, along with consequences of recent work on other polygon classes.
We give a review of results on the minimum convex cover and maximum hidden set problems. In addition, we give some new results. First we show that it is NP-hard to determine whether a polygon has the same convex cover number as its hidden set number. We then give some important examples in which these quantities don't always coincide. Finally, We present some consequences of insights from Browne, Kasthurirangan, Mitchell and Polishchuk [FOCS, 2023] on other classes of simple polygons.