Constant-Factor Approximation Algorithms for Convex Cover and Hidden Set in a Simple Polygon
Reilly Browne, Prahlad Narasimhan Kasthurirangan, Joseph S. B. Mitchell, Valentin Polishchuk
Abstract
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.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
Cited by top-tier papers1
Builds on4
- Maximum Flow and Minimum-Cost Flow in Almost-Linear TimeLi Chen, Rasmus Kyng, Yang P. Liu, Richard Peng et al.FOCS 2022 · 135 citations
- Covering Polygons is Even HarderMikkel AbrahamsenFOCS 2021 · 25 citations
- Approximating Maximum Independent Set for Rectangles in the PlaneJoseph S. B. MitchellFOCS 2021 · 18 citations
- A 3-Approximation Algorithm for Maximum Independent Set of RectanglesWaldo Gálvez, Arindam Khan, Mathieu Mari, Tobias Mömke et al.SODA 2022 · 16 citations
Related papers
- Economical Convex Coverings and ApplicationsSunil Arya, Guilherme Dias da Fonseca, David M. MountSODA 2023 · 1 citation
- Hardness of Packing, Covering and Partitioning Simple Polygons with Unit SquaresMikkel Abrahamsen, Jack StadeFOCS 2024 · 2 citations
- Fast Static and Dynamic Approximation Algorithms for Geometric Optimization Problems: Piercing, Independent Set, Vertex Cover, and MatchingSujoy Bhore, Timothy M. ChanSODA 2025 · 4 citations
- Non-uniform Geometric Set Cover and Scheduling on Multiple MachinesNikhil Bansal, Jatin BatraSODA 2021 · 4 citations
- Minimum Star Partitions of Simple Polygons in Polynomial TimeMikkel Abrahamsen, Joakim Blikstad, André Nusser, Hanwen ZhangSTOC 2024 · 1 citation
