TY - GEN
T1 - Constant-Factor Approximation Algorithms for Convex Cover and Hidden Set in a Simple Polygon
AU - Browne, Reilly
AU - Kasthurirangan, Prahlad Narasimham
AU - Mitchell, Joseph S.B.
AU - Polishchuk, Valentin
N1 - Publisher Copyright: © 2023 IEEE.
PY - 2023
Y1 - 2023
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/85182405191
U2 - 10.1109/FOCS57990.2023.00083
DO - 10.1109/FOCS57990.2023.00083
M3 - Conference contribution
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 1357
EP - 1365
BT - Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023
PB - IEEE Computer Society
T2 - 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023
Y2 - 6 November 2023 through 9 November 2023
ER -